leetcode hot100刷题日记——20.爬楼梯

解答：

直接递归：会超限

class Solution {
public:
    int dfs(int n){
        if(n<=1)
            return 1;
        return dfs(n-1)+dfs(n-2);
    }
    int climbStairs(int n) {
        //dp[i]表示从0爬到i有多少种不同的方法
        //如果最后一步爬了1个台阶，那我们得先爬到i-1，也就是要解决从0爬到i-1有多少种方法
        //如果最后一步爬了2个台阶，那我们得先爬到i-2，也就是要解决从0爬到i-2有多少种方法
        //dp[i]=dp[i-1]+dp[i-2];
        //dp[0]=1,dp[1]=1，从0爬到1也只有1种方法
        //为什么dp[0]=1呢？我觉得更合适的理由是dp[2]=2，那么dp[0]=1
        //用递归法直接做,但是会超限。
        return dfs(n);
    }
};

我们接着看灵茶大大的题解link

方法一：递归+记忆数组

class Solution {
public:
    vector<int>m;
    int dfs(int n){
        if(n<=1){
            return 1;
        }
        int &res=m[n];//表示当递归到n的时候，我们之前存过结果了
        if(res){
            return res;
        }
        return res=dfs(n-2)+dfs(n-1);
    }
    int climbStairs(int n) {
        // 为什么会超限呢？？
        //因为return dfs(i-1)+dfs(i-2);这一步会存在需要递归重复的情况
        //假设n=3
        //return dfs(2)+dfs(1)
        //dfs(2)的时候，dfs(1)+dfs(0)
        //就会有dfs(1)的重复
        //所以我们最好能找个可以记录中间状态和结果的数组
        m.resize(n+1);//为什么这里是n+1呢？比如dfs(2),有dfs(0)要存，dfs(1)要存，dfs(2)也要存，即为n+1
        return dfs(n);
    }
};

在以上方法的基础上，我们在思考可以不用递归的方法:
状态转移方程dp[i]=dp[i-1]+dp[i-2]，直接循环
dp[0]=1,dp[1]=1

class Solution{
public:
	int climbStairs(int n){
		vector<int>dp(n+1);
		dp[0]=dp[1]=1;
		for(int i=2;i<=n;i++){
			dp[i]=dp[i-1]+dp[i-2];
		}
		return dp[n];
	}
};

啧，其实，一开始我还有点迷：
dp[i]=(dp[i-1]+1)+(dp[i-2]+2)
这个式子为啥不对
我当时的想法是，从i-1到i，只有一种走楼梯方式，从i-2到i，有两种走楼梯方式
感觉很合理。
这个问题是在哪里呢？

原问题的正确状态转移方程是 dp[i] = dp[i-1] + dp[i-2]，这是因为：
dp[i-1] 表示从第 (i-1) 阶爬 1 阶到达第 i 阶的方式数。
dp[i-2] 表示从第 (i-2) 阶爬 2 阶到达第 i 阶的方式数。
因此，总的方式数是这两者的累加和。

如果你错误地写成 dp[i] = (dp[i-1] + 1) + (dp[i-2] + 2)，这相当于：
假设从第 (i-1) 阶爬到第 i 阶需要额外增加 1 种方式。
假设从第 (i-2) 阶爬到第 i 阶需要额外增加 2 种方式。
然而，这与问题的实际逻辑不符，因为从 (i-1) 阶到 i 阶的方式数已经由 dp[i-1] 本身涵盖了所有可能的路径，而从 (i-2) 阶到 i 阶的方式数也已经由 dp[i-2] 涵盖了所有可能的路径。额外的 +1 和 +2 是没有依据的。

这种写法会导致错误的结果，因为：
它错误地假设每次爬 1 阶或 2 阶的方式数需要额外增加，而实际上这些方式数已经被之前的递归计算包含了。
它改变了原来累加关系的含义，导致最终的结果不符合实际问题的递推逻辑。

示例验证：
当 n=2 时：
正确的 dp[2] = dp[1] + dp[0] = 1 + 1 = 2。
错误的 dp[2] = (dp[1] + 1) + (dp[0] + 2) = (1 + 1) + (1 + 2) = 5，显然不符合实际情况。
总结，状态转移方程应该严格按照问题的真实逻辑来推导，不能随意添加额外的常数项。