70 爬楼梯
01
题目信息
题目地址：https://leetcode-cn.com/problems/climbing-stairs/
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意： 给定 n 是一个正整数。
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
02
思路一：斐波那契数列
我们可以看先推演几个看看
- 一个台阶：只有一种跳法就是跳一格
- 两个台阶：跳一格跳两次和跳一次2格的
- 三个台阶：1+1+1、2+1、1+2（共三种）
- 四个台阶：1+1+1+1、2+1+1、1+2+1、1+1+2、2+2（共五种）
- 五个台阶 1+1+1+1、2+1+1+1、1+2+1+1、1+1+2+1、1+1+1+2、2+2+1、2+1+2、1+2+2（共八种）
我们可以得到一个规律，他是一个斐波那契数列，题目正整数就不从数列的第0个搞起了直接从第一个开始
台阶数（n） | 方法总数(result) |
|---|---|
1 | 1 |
2 | 2 |
3 | 3 |
4 | 5 |
5 | 8 |
斐波那契数列它是有公式的通过n直接计算出result。
这里我们先假装不知道有公式
我们用迭代的方式推导:
每次要通过前两项记录新的值，再进行迭代直到最后是我们要的第n个。这里有个空间上的注意就是我们不必要记录整个斐波那契数列，只需要保留两个而已。
代码一：
public int climbStairs(int n) {
// 初始值
if(n == 1){
return n;
}
int[] nums = {1,2};
// 上个值与新的值组成新的二元数组
for(int i = 2; i < n; i++){
int temp = nums[0] + nums[1];
nums[0] = nums[1];
nums[1] = temp;
}
return nums[1];
}
总体来说还是不错的，时间O(n)，空间O(1)
然后就是通项公式解，不用说了它最优，不过我们不可忽视的是平方根的复杂度O(logn)。关于这些还有斐波那契状态公式的推导在另外一篇介绍
public int climbStairs(int n) {
double sqrt5 = Math.sqrt(5);
double fibn = Math.pow((1 + sqrt5) / 2, n + 1) - Math.pow((1 - sqrt5) / 2, n + 1);
return (int) Math.round(fibn / sqrt5);
}
03
思路二：动态规划
因为这题比较特殊，其实动态规划的解法代码上面就已经是了但思考的聚焦点不同。这里还是要用这题体会一下动态规划的思路。dp它是一种思想方式，用已知的问题的解解决新问题。递归或者迭代它只是实现这种想法的一种代码书写方式无论我们有没有去做空间优化它都属于这种思想，能压缩空间当然更好。这里先不单独探究这个概念。
那么就是用已解决的问题得出我们的问题解也就是划分子问题，爬第n阶楼梯的方法数量，等于 2 部分之和（就是最后一次的）
爬上 n-1 阶楼梯的方法数量。因为再爬一次1阶就能到第n阶
爬上 n-2 阶楼梯的方法数量。因为再爬一次2阶就能到第n阶
所以我们得到公式
dp[n] = dp[n-1] + dp[n-2]
同时需要初始化
dp[0]=1
dp[1]=2
时间复杂度：O(n)
代码二：
public int climbStairs(int n) {
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 2;
for(int i = 2; i < n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n-1];
}
所以这里就存在空间优化嘛，记录子问题解的时候不需要全部的。用滑动数组的方式只留两个就行了
代码三： 就是解法一上面的解
public int climbStairs(int n) {
if(n == 1) return 1;
int[] dp = {1,2};
for(int i = 2; i < n; i++){
int temp = dp[0] + dp[1];
dp[0] = dp[1];
dp[1] = temp;
}
return dp[1];
}
这样的思路这样的状态式子，我们当然也可以用递归写啊
代码四：
public int climbStairs(int n) {
//递归出口
if(n == 1 || n == 2) {
return n;
}
//过程及主体
return climbStairs(n-1) + climbStairs(n-2);
}
这个东西是有问题待解决的在测试的时候也是超时的，就是我们在动态规划要思考的重复计算的问题，前面是自底向上所以我们每次记录新的二元数组往后继续是线性的，现在自顶向下比如第一层n-1与n-2的情况计算是重复的，我们来画个图看看
首先它不是一线性的，而且两边的计算是重复的，它的时间复杂度是
，它本来一条线复杂度n就算完了但一直有重复计算n长的线变成的n层的树因为他们相互包含。所以我们要把子问题的结果存下来，再有这个不用去重新迭代计算直接取。
代码五：
public int climbStairs(int n) {
int[] mind = new int[n+1];
mind[0] = 1;
mind[1] = 1;
return recur(n,mind);
}
int recur(int n,int[] mind){
//递归出口
if(mind[n] != 0){
return mind[n];
}
//让递归出口不仅仅只有初始值
mind[n] = recur(n-1,mind) + recur(n-2,mind);
return mind[n];
}
现在时间复杂度就变成了O(n)
04
总结
本体是一个经典的动态规划例子，并且还可以转化问题为斐波那契数列的求解那就可以专注线性代数。最优解的通项公式复杂度O(logn)。这题有几个东西还挺有意思的。关于数论矩阵快速幂已加入素材库之后可以演示几个例子，这里的斐波那契数列的通项公式推导可以作为其中一个例子。