动态规划问题--爬楼梯

动态规划问题–爬楼梯

问题要求

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

解决思路

假设 n=9。

我们要解决的问题是从 0爬到 9有多少种不同的方法。

分类讨论：

如果最后一步爬了 7 个台阶，那么我们得先爬到 8 ，要解决的问题缩小成：从 0 爬到 8 有多少种不同的方法。
如果最后一步爬了 2个台阶，那么我们得先爬到 7 ，要解决的问题缩小成：从 0 爬到 7 有多少种不同的方法。
由于这两种情况都会把原问题变成一个和原问题相似的、规模更小的子问题，所以可以用递归解决。

递归算法解决问题

class Solution {
private:
    vector<int> memo;

    int dfs(int i) {
        if (i <= 1) { // 递归边界
            return 1;
        }
        int &res = memo[i]; // 注意这里是引用
        if (res) { // 之前计算过
            return res;
        }
        return res = dfs(i - 1) + dfs(i - 2); // 记忆化
    }

public:
    int climbStairs(int n) {
        memo.resize(n + 1);
        return dfs(n);
    }
};

非递归算法解决问题

当然，该问题也可以使用非递归的算法来解决，如下所示：

class Solution {
public:
    int climbStairs(int n) {
        int p = 0, q = 0, r = 1;
        for (int i = 1; i <= n; ++i) {
            p = q; 
            q = r; 
            r = p + q;
        }
        return r;
    }
};