剑指Offer:跳台阶/变态跳台阶(动态规划解法)
程序员文章站
2022-04-02 21:20:52
...
文章目录
这两题从动态规划的角度思考,按照动态规划的解题框架进行分析,非常的简单和清晰。
跳台阶
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 状态转移方程
2.3 初始值和边界条件
2.4 计算顺序
- 时间复杂度:
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 转移方程
2.3 边界条件和初始值
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];
}