爬楼梯

原题链接

使用的方法

• 动态规划

解题思路

这是一个经典的动态规划问题。我们可以用 dp(n) 表示爬到第 n 个台阶的方法数。
因为每次可以爬 1 或 2 个台阶，所以 dp(n) = dp(n-1) + dp(n-2)。初始条件是 dp(1) = 1，dp(2) = 2。

代码实现

class Solution {
    public int climbStairs(int n) {
        if(n <= 2)
            return n;
        int current = 0;
        int prev2 = 1;
        int prev1 = 2;
        for(int i=3;i<=n;i++){
            current = prev1 + prev2;
            prev2 = prev1;
            prev1 = current;
        }
        return prev1;
    }
}