leetcode70. 爬楼梯 & 剑指 Offer 10- II. 青蛙跳台阶问题题目描述我的解题思路-动态规划

题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

输入：n = 2
输出：2

示例 2：

输入：n = 7
输出：21

示例 3：

输入：n = 0
输出：1

提示：

• 0 <= n <= 100

我的解题思路-动态规划

• 状态: f[i]表示到达i级台阶的方式
• 初始条件; f[0],f[1] = 1
• 转移方程: f[i] = f[i - 1] + f[i - 2],就是到i级台阶的方式可以由到i-1级台阶和i-2级台阶的方式加起来，这转移方程和裴波那契数列的一样。
• 计算顺序: f[0],f[1],…f[n]

代码

class Solution {
    int mod = 1000000007;

    public int numWays(int n) {
        if (n < 2) {
            return 1;
        }
        //f[i]表示跳到i级台阶有多少种方式
        //初始条件: f[0] = 1; f[1] = 1; f[2] = 2;
        //转移方程: f[i] = f[i - 1] + f[i - 2] 解释: 跳到i级台阶的方式可以由跳到i-1级台阶和跳到i-2级台阶之和组成
        int[] f = new int[n + 1];
        f[0] = 1;
        f[1] = 1;
        f[2] = 2;
        for (int i = 3; i <= n; i++) {
            f[i] = (f[i - 1] + f[i - 2]) % mod;
        }
        return f[n];
    }
}

时间复杂度

O(n)

最后

以上就是害羞皮卡丘为你收集整理的leetcode70. 爬楼梯 & 剑指 Offer 10- II. 青蛙跳台阶问题题目描述我的解题思路-动态规划的全部内容，希望文章能够帮你解决leetcode70. 爬楼梯 & 剑指 Offer 10- II. 青蛙跳台阶问题题目描述我的解题思路-动态规划所遇到的程序开发问题。

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