动态规划初步——爬楼梯

题目

    爬楼梯需要 n 阶你才能到达楼顶。每次你可以爬1或2个台阶，有多少种不同的方法可以爬到楼顶呢？

解题思路

    我们用$ f(x)$ 表示爬到第 $x$ 级台阶的方案数，考虑最后一步可能跨了一级台阶，也可能跨了两级台阶，所以我们可以列出如下式子：$$ f(x) = f(x-1) + f(x-2) $$

很好理解，因为每次只能爬 1 级或 2 级，所以$ f(x) $ 只能从$ f(x−1) $和 $f(x−2)$转移过来，而这里要统计方案总数，我们就需要对这两项的贡献求和。即爬到第 $x$ 级台阶的方案数是爬到第 $x−1 $级台阶的方案数和爬到第 $x−2$ 级台阶的方案数的和。

    以上是动态规划的转移方程，下面我们来讨论边界条件。我们是从第 0 级开始爬的，所以从第 0 级爬到第 0 级我们可以看作只有一种方案，即$ f(0)=1$；从第 0 级到第 1 级也只有一种方案，即爬一级，$f(1)=1$。这两个作为边界条件就可以继续向后推导出第 n 级的正确结果。

代码

class Solution {
public:
    int climbStairs(int n) {
        if(n==1) return 1;
        if(n==2) return 2;
        vector<int> nums(n, 0);
        nums[0] = 1;
        nums[1] = 2;
        for(int i=2; i<n; i++){
            nums[i] = nums[i-1] + nums[i-2];
        }
        return nums[n-1];
    }
};