LeetCode/爬楼梯

描述
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

思路
经典动态规划类型题目，这种问题关键在于如何将问题规模缩小并且找到边界
即找到状态转移方程和边界条件
很显然跳第n阶的方法，会等于n-2阶和n-1阶之和
即状态转移方程为dp[n]=dp[n-1]+dp[n-2]
边界为dp[1]=1,dp[2]=2,与斐波那契数列递推基本一致
具体执行可以正向顺序递推，也可以反向递归

之所以能写成dp[n]=dp[n-1]+dp[n-2]进行动态规划和递推
这是求解路径的时候，求的是一个全排列的问题，先跳一步还是先跳两步是两种不同的方案
像凑零钱、背包问题则没有方向和顺序，对应的是一个全组合问题

//其实质上进行的是
        for (int i = 1; i <= n; i++){
            for (int j = 0; j < 2; j++){
                int step = steps[j];
                if ( i < step ) continue;// 台阶少于跨越的步数
                DP[i] = DP[i] + DP[i-step];
            }
//步长位于内循环

//放到外层可以变成求解组合数的问题
for (int j = 0; j < 2; j++){
    int step = steps[j];
    for (int i = 1; i <= n; i++){
        if ( i < step ) continue;// 台阶少于跨越的步数
         DP[i] = DP[i] + DP[i-step];
    }
}

简单的反向递归

class Solution {
public:
    int jumpFloor(int number) {
        if(number==1) return 1;
        if(number==2) return 2;
        return jumpFloor(number-1)+jumpFloor(number-2);
    }
};

优化后的反向递归

class Solution {
public:
    int dp[46]{0};//用备忘录存储减少重复计算
    int climbStairs(int n) {
        if(n<=1) return 1;
        if(dp[n]>0) return dp[n];
        else{
            dp[n]=climbStairs(n-1)+climbStairs(n-2);
            return dp[n];
        }
    }
};

正向递推

class Solution {
public:
    int climbStairs(int n) {
        vector dp(n+2);//类似C语言数组，初始化为0
        dp[1]=1;
        dp[2]=2;
        for(int i=3;i<=n;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
};

--数学方法矩阵快速幂--

接着快速计算矩阵M的n次幂即可得出答案，运用到线代里面的矩阵分解

--数学方法通项公式--