剑指Offer10-Ⅱ 青蛙跳台阶问题

题目

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

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

示例 1：

输入：n = 2
输出：2

示例 2：

输入：n = 7
输出：21

示例 3：

输入：n = 0
输出：1

提示：

0 <= n <= 100

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

多阶段决策:一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶
那么跳上n个台阶需要依赖跳上n-1和n-2个台阶
跳上n-1又需要依赖跳上n-2和n-3台阶
…
跳上3个台阶需要依赖跳上2个台阶和跳上1个台阶
最优解：求一共有多少种跳法，而不是具体的跳法
这是一道多阶段决策求最优解的问题，可以尝试用动态规划做。

动态规划的做题步骤
1.确定dp数组和下标的含义
dp[i]：表示跳上一个i级台阶总共有dp[i]种跳法

2.dp数组递推式
如何跳上一个i级台阶？
可以从i-1个台阶再跳1级
也可以从i-2个台阶再跳2级
所以跳上一个i级台阶的跳法 = 跳上一个i-1个台阶的跳法+跳上一个i-2个台阶的跳法
dp[i]=dp[i-1]+dp[i-2]

3.dp数组的初始化

由递推式dp[i]=dp[i-1]+dp[i-2]可以知道我们需要初始化dp[1]和dp[0]
因为他们两个不能根据递推式推出来(dp[0]=dp[-1]+dp[-2]下标为负了)

dp[1]根据dp数组的定义，非常快能想到dp[1]=1,跳上1级台阶只有一种跳法就是跳1级。
那么dp[0]?跳上0级台阶有几种跳法？我们最开始不就在0级了吗？那么dp[0]=0吗？
其实很多时候dp[0]是没有含义的，需要根据递推式来思考。
什么时候会用到dp[0],dp[2]=dp[1]+dp[0],dp[2]=2,那么dp[0]=1;

这样初始化是因为我们打算从i=2开始给dp数组循环遍历，那么dp[2]=dp[1]+dp[0]

4.dp数组的遍历顺序
根据递推式dp[i]=dp[i-1]+dp[i-2]可以知道，dp[i]的值需要依赖dp[i-1]和dp[i-2],那么i应该从小到大遍历

for(let i=2;i<n+1;i++){//根据定义我们求的是dp[n]，所以i<n+1
dp[i] = (dp[i-1] + dp[i-2])%1000000007;
}

代码

var numWays = function(n) {
let dp =[];
dp[0] = 1;
dp[1] = 1;
for(let i=2;i<n+1;++i){
dp[i] = (dp[i-1] + dp[i-2])%1000000007;
}
return dp[n];
};

空间优化

dp[i]=dp[i-1]+dp[i-2]，dp[i]的值需要依赖dp[i-1]和dp[i-2]，可以模拟以下赋值的过程，发现当前值只依赖于前一个值和再前一个值，我们可以使用变量来存储这两个值，就不用使用数组了。

var numWays = function(n) {
[pre,cur] = [1,1];//cur表示前一个值dp[i-1]，pre表示前一个值dp[i-2]
for(let i=2;i<n+1;++i){
let tmp = cur;//存储dp[i-1]的值 此时pre=dp[i-2]的值
cur=(cur+pre)%1000000007; //dp[i]=dp[i-1]+dp[i-2],cur赋值之后是dp[i]的值，不是dp[i-1]的值了
pre = tmp;//tmp是dp[i-1]的值
//对于下一次循环来说(++i),dp[i+1]=dp[i]+dp[i-1],所以把pre的值修改成dp[i-1]，cur的值修改成dp[i]
}
return cur;
};

最后

以上就是香蕉吐司为你收集整理的剑指Offer10-Ⅱ 青蛙跳台阶问题剑指Offer10-Ⅱ 青蛙跳台阶问题的全部内容，希望文章能够帮你解决剑指Offer10-Ⅱ 青蛙跳台阶问题剑指Offer10-Ⅱ 青蛙跳台阶问题所遇到的程序开发问题。

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