题目描述:
剑指offer的题目:跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
对应leetcode题目70. Climbing Stairs
思想
这题蕴含很重要的动态规划的思想.
要理解动态规划首先要明白一个事情: 动态规划和动态编程之类的没什么关系.
动态规划的实质是一种表格法, 和动态关系不大. 以后直接把动态规划和表格法等价起来就好了.
可以用来优化递归.
题目分析
解动态规划的套路可以首先找递归解法, 然后把递归里重复的子问题记下来,放在数组里面, 避免重复的计算. 然后可以进一步的把记录结果的数组优化成滚动数组.
递归解法
对于这个题目, 首先我们当前有n个台阶, 可以选择跳一次跳一个台阶或者一次跳两个台阶.
- 如果我选择1个台阶: 那么还剩下n-1个台阶
- 如果我选择2个台阶: 那么还剩下n-2个台阶
那我的所有选择就是两种情况的相加
考虑两个极端情况:
- 总共只有0或1个台阶 我只有一个选择, 那就是跳
因此可以有递归解法:
class Solution {
public:
int jumpFloor(int number) {
if(number <2){
//0,1
return 1;
}
// 跳一阶的选择
int jump1 = jumpFloor(number-1);
// 跳二阶的选择
int jump2 = jumpFloor(number-2);
// 选择之和
return jump1+jump2;
}
};
非递归解法
递归解法的时间空间复杂度总是不尽如人意, 毕竟要递归.
而对这个问题来说, 每次调用的jumpFloor其实存在很多此重复调用: 计算第n阶的时候需要n-1和n-2阶的结果, 而n-1阶结果的计算依赖于n-2和n-3阶的结果, 这里n-2就被重复计算了. 随着递归深入, 其实除了最后的第n阶结果本身以外都被重复的计算了. 这就是重叠子问题, 而其实n-2阶的结果不管是算几次都是一样的结果.
因此我们可以根据这个的特性, 将每一阶的结果记下来.
或者, 干脆考虑自底向上的解法, 从第1阶开始算:
class Solution {
public:
int jumpFloor(int number) {
if(number <2){
//0,1 阶的时候都只要跳一次即可
return 1;
}
// 简单版本 自底向上保留全部结果
// 加上默认的0阶和一阶的结果
int *result = new int[number+1]{1,1};
// 从第2阶开始计算
for (int i=2;i<=number;++i){
result[i] = result[i-1]+result[i-2];
}
return result[number];
}
};
时间复杂度:O(N) 空间复杂度:O(N)
数组优化
因为我们每次循环其实只关心当前台阶数-1和当前台阶数-2的时候需要跳几次, 再往前的我们就不关心了(因为一次只能跳一阶或者两阶, 对应台阶数只能-1或者-2, 多了也没用).
因此我们可以把记录所有的楼层数的数组优化成只记录前两阶的长度为2的数组. 这种数组称为滚动数组, 里面永远记录者当前阶数-1和当前阶数-2需要跳的次数. 这样做就可以将空间复杂度降成常数级.
每次只记录上两个项, 时间复杂度:O(N) 空间复杂度:O(1)
class Solution {
public:
int jumpFloor(int number) {
if(number <2){
//0,1
return 1;
}
// 滚动数组, 每次只记录上两个
int *result = new int[2]{1,1};
int current = 0;
for (int i=2;i<=number;++i){
current = result[0]+result[1];
result[0]= result[1];
result[1]= current;
}
return current;
}
};
进阶版: 每次可以跳1-n阶
其实就是把每次加上两阶改成每次加所有:
class Solution {
public:
int jumpFloorII(int number) {
if (number <2){
return 1;
}
int* result = new int[number+1]{1,1};
// 每次把所有可能的情况加起来, 即 1,2,3,...,n-1的所有可能相加
for (int i=2;i<=number;++i){
int current = 0;
for (int j=0;j<i;++j){
current += result[j];
}
result[i]=current;
}
return result[number];
}
};
Last modified on 2020-03-29