LeetCode-剑指10-II.青蛙跳台阶问题1、动态规划法2、动态规划法优化

1、动态规划法

我们可以使用数组dp用于距离跳上每一级台阶可能的跳法。其中状态转化方程为：$dp[i]=(dp[i-1]+dp[i-2])\%1000000007$。

class Solution {
public:
    int numWays(int n) {
        if (n < 2) return 1;
        vector<int> dp(n + 1, 1);
        dp[2] = 2;
        for (int i = 3; i <= n; ++i) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
        }
        return dp[n];
    }
};

2、动态规划法优化

考虑到实际上我们的数组只使用到最后两位，我们可以使用三个变量来代替数组。

class Solution {
public:
    int numWays(int n) {
        if (n < 2) return 1;
        int p = 0, q = 1, r = 2;
        for (int i = 3; i <= n; ++i) {
            p = q;
            q = r;
            r = (p + q) % 1000000007;
        }
        return r;
    }
};

最后

以上就是想人陪大白为你收集整理的LeetCode-剑指10-II.青蛙跳台阶问题1、动态规划法2、动态规划法优化的全部内容，希望文章能够帮你解决LeetCode-剑指10-II.青蛙跳台阶问题1、动态规划法2、动态规划法优化所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。