LeetCode 70：爬楼梯，从 dp[i] 含义推出一维 DP
题目要求 输入输出 输入：整数 n 含义：爬到第 n 阶楼顶 每次可以爬 1 或 2 阶 输出：返回到达楼顶的不同走法数量 约束：1 <= n <= 45 示例 输入：n = 2 输出：2 解释：1+1，2 输入：n = 3 输出：3 解释：1+1+1，1+2，2+1 这篇只用 Python，从 dp[i] 的含义一步一步推出最终代码。 从 n = 3 的最后一步开始 先看最小能暴露转移的例子： n = 3 到第 3 阶的最后一步只可能来自： 第 2 阶，再走 1 阶 第 1 阶，再走 2 阶 所以“到第 3 阶的方法数”不是凭空算出来的，而是来自两个更小的位置。 Step 1：先定义更小的问题 直接问“到第 n 阶有几种走法”太大。先定义： dp[i] = 到达第 i 阶的方法数 注意这里的 i 是楼梯位置，不是数组下标含义上的第几个元素。 ...