这两题从动态规划的角度思考，按照动态规划的解题框架进行分析，非常的简单和清晰。

跳台阶

1. 题意

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

2. 分析

2.1 确定状态

2.1.1 最后一步

• 先不管前面是是如何跳跃的，最后一定会跳跃到台阶n
• 根据题目的描述，青蛙只可能从台阶n-1或者台阶n-2跳跃到台阶n
• 那么如果我知道了有多少种跳法能跳到台阶n-1和台阶n-2，那么跳到台阶n的跳法自然也就出来了，就是二者之和

2.1.2 子问题

• 原问题是求，有多少种跳法跳到台阶n
• 现在要解决这个原问题，只需要知道有多少种跳法跳到台阶n-1和台阶n-2
• 问题不变，但问题规模变小了，那么状态也就定义出来了
• f[i]表示有几种跳法能够跳到台阶i，最后返回f[n]即是答案

2.2 状态转移方程

$$f[i]=f[i-1]+f[i-2]（i>1）$$

2.3 初始值和边界条件

• $f[0]=1,跳到台阶0只有一种跳法，那就是不跳$
• $f[1]=1,跳到台阶1，也只有一种跳法，那就是跳1级$

2.4 计算顺序

• $f[0,1,2,........n]$
• 时间复杂度：O(n)
• 空间复杂度：O(n)，因为只需要开一个长度为n+1的数组

3. 代码

public int JumpFloor(int target) {
int[] f = new int[target + 1];
f[0] = 1;
f[1] = 1;
for (int i = 2; i <= target ; i++) {
f[i] = f[i-1] + f[i-2];
}
return f[target];
}

变态跳台阶

1. 题意

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

2.分析

2.1 确定状态

2.1.1 最后一步

• 与上题完全一样，不管前面怎么跳，最后一定能跳到台阶n
• 根据题意，一只青蛙可以跳上1级、2级…n级台阶
• 那么最后一步跳到台阶n的就可能是台阶n-1,台阶n-2...............台阶0
• 那么我只需要知道跳到台阶n-1、台阶n-2、.......、台阶0各有多少种跳法，跳到台阶n的跳法也就是他们之和

2.1.2 子问题

• 原问题是求，有多少种跳法跳到台阶n
• 现在要解决这个原问题，只需要知道有多少种跳法跳到台阶n-1、台阶n-2、.......台阶0
• 问题不变，但问题规模变小了，那么状态也就定义出来了
• f[i]表示有几种跳法能够跳到台阶i，最后返回f[n]即是答案

2.2 转移方程

$$f[i]=f[i-1]+f[i-2]+....+f[0]$$

2.3 边界条件和初始值

• $f[0]=1,跳到台阶0只有一种跳法，那就是不跳$
• $f[1]=1,跳到台阶1，也只有一种跳法，那就是跳1级$

2.4 计算顺序

• 同上
• 时间复杂度

3. 代码

public int JumpFloorII(int target) {
int[] f = new int[target +1];
//0层不跳也是一种跳法
f[0] = 1;
f[1] = 1;
for (int i = 2; i <= target ; i++) {
for (int j = i -1;j >= 0; j-- ){
f[i] += f[j];
}
}
return f[target];
}

最后

以上就是自信小蜜蜂为你收集整理的剑指Offer:跳台阶/变态跳台阶(动态规划解法)跳台阶变态跳台阶的全部内容，希望文章能够帮你解决剑指Offer:跳台阶/变态跳台阶(动态规划解法)跳台阶变态跳台阶所遇到的程序开发问题。

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