爬楼梯问题
接触DP最早的应该就是这道题了吧，翻了翻leetcode submission发现最早的是在一年前... 而且是最基础的DP解法。在膜拜了大神们用矩阵甚至直接上斐波那契数列公式解法后觉得脑容量有点不太够用。。。嗯，需要写点东西捋一捋，所以这是一个学渣（p.s. 话痨）关于爬楼梯类型题目的总结（如果有不对的地方欢迎米娜桑批评指正(￣.￣)）。
题目：Climbing Stairs
You are climbing a stair case. It takes n steps to reach to the top.Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Input：
Argument：达到最高层的步数（Integer）
Condition： 每次只能爬一步或者两步
Output:
达到最高层可以用多少种不同的方法(Integer)
1. 暴力递归
Intuitive:
想法很简单，既然下一步只有两种选择：1步和2步， 那么下步走的方法也就是2种。总的方法数即走一步的方法 + 走两步的方法。
Edge cases:
当前走的步数等于或者大于0时结束递归
Recursion Tree
例如目标层数是5，那么recursion tree应该是这个样子滴
image.png
可以看到每个节点我们都有两个选择，走一步或者两步。那么一共有 2^n 个节点，时间复杂度 2^n. 至于空间复杂度则是树的深度，最坏的情况，我们每次只走一步，深度达到n。另外也不难看出在递归的过程中存在很多重复的计算，这就是下一个算法优化的点啦。
Code：
TC:O(2^n) SC:O(n)
public int climbStairs(int target){
return helper(0, target);
}
public int helper(int step, int target){
//edge cases
if(step == target){
return 1;
}
if(step > target){
return 0;
}
return helper(step + 1, target) + helper(step + 2, target);
}
2. 记忆化搜索
Intuitive:
所以，怎么避免重复计算呢？很明显的想法就是把算过的存起来嘛，下次计算前先查一下，有结果就跳过，没结果就算。就是这样一个小小的优化， 就把复杂度从2^n缩减到n(p.s. array 查询的复杂度是O(1)),你敢信！嗯，所以在面试官followup的时候，别老想有多fancy或者tricky的变化，逮着最明显的那个劣势优化就好~
Edge cases:
Edge case 是跟暴力递归的一样的。
Code:
TC: O(n) SC: O(n)
public int climbStairs(int target){
int[] memo = new int[target + 1];
return helper(0, target, memo);
}
public int helper(int step, int target, int[] memo){
if (memo[step] != 0){
return memo[step];
}
if(step == target){
return 1;
}
if(step > target){
return 0;
}
memo[i] = helper(step + 1, target, memo) + helper(step + 2, target, memo);
return memo[i];
}
3. 动态规划
Intuitive:
那么就来到高大上的DP了，曾经有一度我都认为按照我的水平面试如果遇到DP的题就基本可以跪了。虽然现在依然有点怵，但是发现DP他不是玄学，一上来就给你整个高大上的状态转移方程，自然会一脸懵逼。但是，如果了解了DP是怎么从暴力递归，记忆化搜索一步步进化而来的，那么就可以不再害怕DP这个磨人的小妖精啦。不记得从哪里看到一句话，DP是一种思想而不是算法，嗯，所以要想的多...
DP的本质就是当前结果依赖于之前结果，或者说子问题。那么我们在第i步时候的方法数就依赖于之前走的步数，在这道题就是:
dp[i] = dp[i - 1] + dp[i - 2]
Edge Cases:
那么edge cases 就很明显了，总不能让index小于0吧╮(－_－)╭。
- dp[1] = 1
- dp[2] = 2
Code:
TC: O(n) SC:O(n)
public int climbStairs(int target){
if (target == 1 || target == 2){
return target;
}
int[] dp = new int[target + 1];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= target; i++){
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[target];
}
其实关于动态规划和记忆搜索的区别，我并不是分的很清楚，有的资料说一个是top down一个是bottom up。嗯，那么对于倒着填的DP又该怎么解释呢？在这里mark一下，以后找找资料做个记忆化搜索和动态规划的比较v(￣︶￣)y
其实从状态转移方程不难看出来，结果dp[i]只依赖于前两个数dp[i - 1]和dp[i - 2]。所以在不要求打印路径的情况下，我们真的需要一个O(n)的空间么？是不是只要维护两个变量滚动更新就好了？那么之前的DP解法可以进一步简化了。
Code:
TC: O(n) SC:O(1)
public int climbStairs(int target){
if (target == 1 || target == 2){
return target;
}
int pre1 = 1;
int pre2 = 2;
for (int i = 3; i <= target; i++){
int temp = pre1 + pre2
pre1 = pre2;
pre2 = temp;
}
return pre2;
}
4. 矩阵解法
Here comes the fun part~~~ (=￣ω￣=)
其实这部分才是我写这篇又臭又长的博文的动机所在，那么就让我试试用我捉襟见肘的语言表达能力和惨不忍睹的数学功底能不能解释清楚吧...
从之前的DP解法我们知道递推公式是这样滴：
f(n) = f(n - 1) + f(n - 2)
那么对于这样一个二阶的递推公式我们能不能借用一个二阶的矩阵来表示这个递推关系呢？试一试哈,设我们的谜之矩阵为
image.png
我们想促成这样的一个表达式：
image.png
已知的一些关系为：
f(1) = 1
f(2) = 2
f(3) = 3
f(4) = 5
把这些已知的数代入这个递推关系式中：
image.png
四个未知数四个方程，那么可以求出谜之矩阵为
image.png
那么通式为：
image.png
通式右边的部分我们可以继续用公式替换：
例如把：
image.png
代入通式，得：
image.png
以此类推通式可以化简为：
image.png
那么原问题就可以被转化成求二阶矩阵n - 2次方的问题了。先不考虑矩阵，从最简单的来哈，如果求一个数的n次方，让你用O(lgn)的算法求出，最直接的想法是什么？没错转化成二进制计算。
举个例子, 求10 ^ 35, 可以分解为：
image.png
而35转化为二进制为：
image.png
不难看出，只有在二进制位上是1的时候我们才需要乘以该位对应的数值，而遇到为0的情况就直接skip，运算次数减少了很多呀。
那么对于矩阵的乘法也是一样的道理滴。最多需要你implement一个计算两个矩阵相乘的helper function 而已。时间复杂度分析也很清楚了，矩阵的n次方可以由矩阵n/2次方的平方得出，以此类推可以有这样一个recrusion tree：
image.png
树的高度是lg(n), 那么我们需要做的乘法是也就是lg(n)次。
Edge Cases:
与之前差不多
Code:
TC: O(lg(n)) SC:O(1)
public int climStairs(int target){
if(target < 1){
return 0;
}
if (target == 1 || target == 2){
return target;
}
int[][] matrix = {{1, 1},{1, 0}};
int[][] res = matrixPow(matrix, target - 2);
//别忘记乘以最开始的f(2) 与 f(1)
return res[0][0] * 2 + res[0][1] * 1;
}
//计算矩阵 n 次方
public int[][] matrixPow(int[][] matrix, int n){
int r = matrix.length;
int c = matrix[0].length;
int[][] res = new int[r][c];
//单位矩阵
for (int i = 0; i < r; i++){
res[i][i] = 1;
}
int[][] placeHolder = matrix;
for(; n > 0; n >>>= 1){
if ((n & 1) == 1){
res = matrixMulti(res, placeHolder);
}
placeHolder = matrixMulti(placeHolder, placeHolder);
}
return res;
}
//计算两矩阵相乘
public int[][] matrixMulti(int[][] m1, int[][] m2){
int m1Row = m1.length;
int m1Col = m1[0].length;
int m2Col = m2[0].length;
int[][] res = new int[m1Row][m2Col];
for (int i = 0; i < m1Row; i++){
for (int k = 0; k < m1Col; k++){
if (m1[i][k] != 0){
for (int j = 0; j < m2Col; j++){
if(m2[k][j] != 0){
res[i][j] += m1[i][k] + m2[k][j];
}
}
}
}
}
return res;
}
5. 斐波那契公式解法
最后一种是借助用斐波那契数列的解来解题，更多数学...
为了方便用二元一次方程的通解我们把斐波那契的公司小小改动一下，表达的意思还是一样的哈:
image.png
image.png
则原方程转化为：
image.png
两边都除以相同项得：
image.png
套用二元一次方程通解得：
image.png
则f(n) 可以写为：
image.png
代入已知的f(0) = 0, f(1) = 1等... 可得：
image.png
代入之前的公式得：
image.png
大功告成~ 所以code也就是直接套用这个公式一下就好，偷个懒不写了。另外从这个公式也不难看出斐波那契数列问题如果用brute force方法解的话复杂度是2^n的。
补充：
嗯，之所以花时间来总结这个题，就是因为很多DP的题其实本质就是个爬楼梯问题，或者说本质就是斐波那契数列问题。那么只要我们了解了这个方法论之后，那么在遇到类似的题目就可以见招拆招，万变不离其宗啦。
举个🌰：
有一对兔子，每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？
贡献于第n个月的兔子数量的是f(n - 1) + f(n - 3)
递推公式是 f(n) = f(n - 1) + f(n - 3)
那么三阶递推公式就可以试试用三阶递推矩阵表示了，其余的步骤就大同小异啦。
Reference:
https://discuss.leetcode.com/topic/30625/easiest-java-solution
https://leetcode.com/problems/climbing-stairs/solution/
