【动态规划-1】 70. 爬楼梯（动态规划系列开篇）_爬楼梯 动态规划

70. 爬楼梯

难度：简单
力扣地址：https://leetcode.cn/problems/climbing-stairs/submissions/545614130/

1. 问题描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。

1. 1 阶 + 1 阶
2. 2 阶

示例 2：

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。

1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

2. 问题分析

首先我们需要得到如下两个结论：

1. n = 1 时，result = 1，仅有一种可能；n = 2 时，result = 2，注意这个台阶可能是 1 + 1得到的，也可能是 0 + 2 得到的；类似地，当 n >= 2 以后，每个台阶都有两种可能，也就是说，从 n - 2 台阶过来的 与 从 n - 1 台阶过来的。
2. 总共爬 n 个台阶，它一定与 n - 1 台阶的方法数目、n - 2 台阶的方法数目有关（与结论1相互照应）。

接下来，我们如果用 dp[n] 表示爬 n 个台阶的总共方法数目，那么接下来需要了解 dp [n] 与 dp [n-1] 以及 dp [n - 2] 之间的关系。

先写几个例子：

• dp[3] = 3 = dp[1] + dp[2]
• dp[4] = 6 = dp[2] + dp[3]
• dp[5] = 9 = dp[3] + dp[4]

看起来很明显，dp[n] = dp[n-1] + dp[n-2] 。而且也很容易理解，因为 第 n 台阶可能是从第 n - 1个台阶上来的，也有可能是从第 n - 2 个台阶上来。

但是我们是讲究人，我们证明一下：

要证明 ( dp[n] = dp[n-1] + dp[n-2] )，我们可以通过分析题目中的爬楼梯过程来直观地理解这个递推关系。

证明过程

假设到达第 ( $n$ ) 阶有 ( $dp[n]$ ) 种不同的方法。为了到达第 ( $n$) 阶，最后一步可能是从第 ($n-1$) 阶跨一步上来的，或者是从第 ( $n-2$) 阶跨两步上来的。

情况1：最后一步从第 ( $n-1$) 阶跨一步到第 ( $n$ ) 阶

如果最后一步是从第 ( $n-1$ ) 阶跨一步到第 ( $n$) 阶，那么到达第 ( $n-1$) 阶的方法数就是 ( $dp[n-1]$)。因为只需要再跨一步就可以到达第 ( $n$ ) 阶，所以这种情况下的方法数就是 ( $dp[n-1]$)。

情况2：最后一步从第 ( $n-2$ ) 阶跨两步到第 ( $n$ ) 阶

如果最后一步是从第 ( $n-2$ ) 阶跨两步到第 ( $n$ ) 阶，那么到达第 ( $n-2$) 阶的方法数就是 ( $dp[n-2]$)。因为只需要再跨两步就可以到达第 ( $n$ ) 阶，所以这种情况下的方法数就是 ( $dp[n-2]$ )。

由于这两种情况是互斥的，即每种方法要么最后一步是从第 ( $n-1$ ) 阶跨一步上来的，要么是从第 ( $n-2$) 阶跨两步上来的，所以到达第 ( $n$ ) 阶的所有方法数就是这两种情况的方法数之和。

数学表达式

因此，可以得到以下递推关系：

$[dp[n]=dp[n-1]+dp[n-2]]$

初始条件

为了让递推关系成立，我们还需要给出初始条件：

• 当 ( n = 0 ) 时，只有一种方法，即不动，所以 ( dp[0] = 1 )。
• 当 ( n = 1 ) 时，也只有一种方法，即跨一步，所以 ( dp[1] = 1 )。

3. 代码编写

现在我们拿到了法宝：dp[n] = dp[n-1] + dp[n-2]，并且 dp[1] = 1，dp[2] = 2 ，要求解 dp[n] ，那就非常简单了。

class Solution {
public:
    int climbStairs(int n) {
        if (n == 1) {   return 1;   }
        vector<int> dp(n + 1, 1);
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13

第一次提交的时候报错，数组越界。发现我没有排除 n = 1 的情况，所以在第一行添加即可，

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

4. 优化 —— 节省空间

因为求解 dp[n] 时，只需要考虑 dp[n-1] 与 dp[n-2] ，所以其实不需要申请一个长度为 n + 1的空间。

class Solution {
public:
    int climbStairs(int n) {
        if (n == 1) {   return 1;   }

        int dp1 = 1;
        int dp2 = 2;

        for (int i = 3; i <= n; i++) {
            int dpi = dp1 + dp2;
            dp1 = dp2;
            dp2 = dpi;
        }
        return dp2;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

5. 总结

麻雀虽小五脏俱全。从“爬楼梯”这道题中，我们可以学到动态规划的一些基础知识和思想，灵活应用这些思想非常非常困难，但是一定一定要先了解了解，要不然看答案也不能理解（自画像了属于是）。

我们解刨一下小麻雀，看看有哪些具体内容：

1. 问题的分解

动态规划的核心思想是将一个复杂的问题分解成更小的子问题，通过解决这些子问题来构建原问题的解。在爬楼梯问题中，我们将到达第 ( n ) 阶楼梯的方法数分解成到达第 ( n-1 ) 阶和第 ( n-2 ) 阶的方法数之和。

2. 状态定义

动态规划中的每一个状态都代表了原问题的一个子问题。我们需要明确状态的定义。在爬楼梯问题中，我们定义 ( dp[i] ) 为到达第 ( i ) 阶楼梯的方法数。

3. 状态转移方程

状态转移方程是动态规划的核心，通过状态转移方程我们可以从已知的状态推导出未知的状态。在爬楼梯问题中，状态转移方程为：

[ dp[i] = dp[i-1] + dp[i-2] ]

4. 初始条件

为了让状态转移方程生效，我们需要确定一些初始条件，这些初始条件通常是问题的最简单形式。在爬楼梯问题中，初始条件为：

• dp[0] = 1
• dp[1] = 1

5. 重复子问题

动态规划通常用来解决那些具有重复子问题性质的问题。在爬楼梯问题中，到达某一阶的方法数可以通过到达之前几阶的方法数来计算，而到达之前几阶的方法数会被多次使用。

6. 递归和记忆化（Memoization）

动态规划可以通过递归的方式来实现，并使用记忆化技术来避免重复计算。爬楼梯问题中，可以使用递归加上记忆化数组来记录已经计算过的结果。

7. 自底向上（迭代）方法

除了递归加记忆化的方法，动态规划也可以用迭代的方式自底向上计算。在爬楼梯问题中，我们可以用一个循环从 ( dp[2] ) 开始，逐步计算到 ( dp[n] )。

8. 空间优化

很多动态规划问题可以通过优化空间复杂度来提升效率。在爬楼梯问题中，我们注意到计算 ( dp[i] ) 只需要 dp[i-1] 和 dp[i-2] ，因此可以用两个变量代替整个数组，优化空间复杂度为 (O(1))。

为了看五脏，我也算是真的够残忍了。

感谢各位的点赞支持，非常感谢 ~

Smileyan
2024.07.10 23:23