70. 爬楼梯

动态规划

class Solution {
    public int climbStairs(int n) {

        /**
         * 动态规划
         * climbStairs(n)只与climbStairs(n - 1)和climbStairs(n - 2)有关，因此不需要存储所有的值，只用两个变量存储这两个值
         * n从1开始
         */
        if (n <= 2){
            return n;
        }

        int[] dp = new int[3];
        dp[0] = 1;
        dp[1] = 2;
        dp[2] = 0;

        for (int i = 3; i <= n; i++) {

            dp[2] = dp[0] + dp[1];
            dp[0] = dp[1];
            dp[1] = dp[2];
        }

        return dp[1];
    }
}

/**
 * 时间复杂度 O(n)
 * 空间复杂度 O(1)
 */

https://leetcode-cn.com/problems/climbing-stairs/