动态规划（Dynamic Programming, DP）是一种强大的算法设计技术，常用于解决具有重叠子问题和最优子结构性质的优化问题。在众多算法问题中，“攀登楼梯”问题是理解动态规划概念的一个绝佳入门案例。本文将深入探讨攀登楼梯问题，并详细介绍如何运用动态规划来寻找最优解，助您在算法学习的道路上更进一步。攀登楼梯问题不仅是动态规划的经典案例，也是面试中常见的一道算法题，掌握其解法对于提升算法能力至关重要。本文将从问题定义入手，逐步推导出动态规划的解题思路，并提供多种实现方案。通过学习本文，您将能够：理解动态规划的核心思想；掌握攀登楼梯问题的多种解法；提升解决复杂优化问题的能力；为应对算法面试做好充分准备。
关键要点
问题定义： 攀登楼梯问题描述的是，给定一个 n 阶楼梯，每次可以爬 1 阶或 2 阶，求有多少种不同的方法可以爬到楼顶。
状态转移方程： 动态规划的核心在于状态转移方程。对于攀登楼梯问题，dp[i] 表示爬到第 i 阶楼梯的不同方法数，则状态转移方程为 dp[i] = dp[i-1] + dp[i-2]。
边界条件： 为了正确计算状态转移方程，需要定义边界条件。通常，dp[0] = 1 表示爬到第 0 阶楼梯（即起点）有一种方法，dp[1] = 1 表示爬到第 1 阶楼梯有一种方法。
动态规划解法： 根据状态转移方程和边界条件，可以自底向上地计算 dp 数组，最终 dp[n] 即为所求结果。
优化技巧： 针对攀登楼梯问题，可以采用滚动数组或变量来降低空间复杂度，将空间复杂度从 O(n) 优化到 O(1) 。
应用场景： 攀登楼梯问题看似简单，但其思想可以应用于解决其他类似的优化问题，例如斐波那契数列、路径计数等。
攀登楼梯问题详解
攀登楼梯问题：定义与理解
攀登楼梯问题是一个经典的动态规划问题，它描述了一个人要爬上一个共有 n 阶的楼梯。这个人可以选择每次爬 1 阶或者 2 阶。我们需要找出总共有多少种不同的方法可以爬到楼梯的顶部。
☞☞☞AI 智能聊天, 问答助手, AI 智能搜索, 多模态理解力帮你轻松跨越从0到1的创作门槛☜☜☜
这个问题看似简单，但实际上它完美地展示了动态规划的核心思想。理解这个问题不仅能帮助我们掌握动态规划，还能为解决其他类似的算法问题打下坚实的基础。
问题描述：
给定一个 n 阶楼梯，每次可以爬 1 阶或 2 阶，求有多少种不同的方法可以爬到楼顶。
示例：
-
n = 2
输出：2
解释：有两种方法可以爬到楼顶。
- 1 阶 + 1 阶
- 2 阶
-
n = 3
输出：3
解释：有三种方法可以爬到楼顶。
- 1 阶 + 1 阶 + 1 阶
- 1 阶 + 2 阶
- 2 阶 + 1 阶
理解问题：
要解决这个问题，首先要理解问题的本质。当我们要爬到第 n 阶楼梯时，我们有两种选择：
- 从第 n-1 阶爬 1 阶到达第 n 阶。
- 从第 n-2 阶爬 2 阶到达第 n 阶。
因此，爬到第 n 阶楼梯的方法总数等于爬到第 n-1 阶的方法数加上爬到第 n-2 阶的方法数。这就是动态规划的核心思想：将一个大问题分解成若干个子问题，并利用子问题的解来求解原问题。
动态规划解题思路：状态转移方程
动态规划解题的核心在于确定状态转移方程。状态转移方程描述了如何从子问题的解推导出原问题的解。在攀登楼梯问题中，我们可以定义以下状态：
- dp[i]： 爬到第 i 阶楼梯的不同方法数。
根据问题的描述，我们可以得到以下状态转移方程：
- dp[i] = dp[i-1] + dp[i-2]
这个状态转移方程表示，爬到第 i 阶楼梯的方法数等于爬到第 i-1 阶的方法数加上爬到第 i-2 阶的方法数。为了正确计算状态转移方程，我们需要定义边界条件：
- dp[0] = 1： 爬到第 0 阶楼梯（即起点）有一种方法。
- dp[1] = 1： 爬到第 1 阶楼梯有一种方法。
有了状态转移方程和边界条件，我们就可以自底向上地计算 dp 数组，最终 dp[n] 即为所求结果。
动态规划求解过程：
- 初始化 dp 数组，设置边界条件 dp[0] = 1 和 dp[1] = 1。
- 从 i = 2 开始，依次计算 dp[i]，直到 i = n。
- 计算 dp[i] 的值为 dp[i-1] + dp[i-2]。
- 返回 dp[n]，即为所求结果。
通过动态规划，我们可以高效地解决攀登楼梯问题。下面我们将介绍如何用代码实现动态规划解法。
代码实现：多种编程语言示例
下面我们提供多种编程语言的代码示例，展示如何用动态规划解决攀登楼梯问题。
1. C++ 代码：
#include <iostream>
#include <vector>
using namespace std;
int climbStairs(int n) {
if (n <= 1) {
return 1;
}
vector<int> dp(n + 1);
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; ++i) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
int main() {
int n = 5;
cout << "Number of ways to climb " << n << " stairs: " << climbStairs(n) << endl;
return 0;
}
2. Python 代码：
def climbStairs(n):
if n <= 1:
return 1
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
n = 5
print(f"Number of ways to climb {n} stairs: {climbStairs(n)}")
3. Java 代码：
public class ClimbStairs {
public static int climbStairs(int n) {
if (n <= 1) {
return 1;
}
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; ++i) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
public static void main(String[] args) {
int n = 5;
System.out.println("Number of ways to climb " + n + " stairs: " + climbStairs(n));
}
}
代码解释：
- 代码首先处理边界条件，即 n
- 然后，创建一个 dp 数组，用于存储中间结果。
- 初始化 dp[0] 和 dp[1] 的值为 1。
- 从 i = 2 开始，依次计算 dp[i]，值为 dp[i-1] + dp[i-2]。
- 最终返回 dp[n]，即为所求结果。
这些代码示例展示了如何用不同的编程语言实现动态规划解法。通过这些示例，您可以更好地理解动态规划的实现过程。
空间复杂度优化：滚动数组与变量
动态规划解法的时间复杂度为 O(n)，空间复杂度也为 O(n)，因为我们需要创建一个大小为 n+1 的 dp 数组。但是，我们可以通过使用滚动数组或变量来降低空间复杂度，将空间复杂度从 O(n) 优化到 O(1)。
1. 滚动数组优化：
由于 dp[i] 的值只依赖于 dp[i-1] 和 dp[i-2]，因此我们只需要保存最近的两个状态即可。可以使用一个大小为 3 的数组来存储这些状态，并不断更新这些状态。以下是 C++ 代码示例：
int climbStairs(int n) {
if (n <= 1) {
return 1;
}
vector<int> dp(3);
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; ++i) {
dp[i % 3] = dp[(i - 1) % 3] + dp[(i - 2) % 3];
}
return dp[n % 3];
}
2. 变量优化：
更进一步，我们只需要保存最近的两个状态值，可以使用两个变量来存储这些状态，并不断更新这些变量。以下是 C++ 代码示例：
int climbStairs(int n) {
if (n <= 1) {
return 1;
}
int a = 1, b = 1;
for (int i = 2; i <= n; ++i) {
int temp = a + b;
a = b;
b = temp;
}
return b;
}
这两种优化方法都将空间复杂度降低到 O(1)，使得代码更加高效。在实际应用中，可以根据具体情况选择合适的优化方法。
动态规划的应用：斐波那契数列
攀登楼梯问题与斐波那契数列有着密切的联系。实际上，攀登楼梯问题的解法就是斐波那契数列的递推公式。斐波那契数列定义如下：
- F(0) = 0
- F(1) = 1
- F(n) = F(n-1) + F(n-2) （n >= 2）
我们可以看到，斐波那契数列的递推公式与攀登楼梯问题的状态转移方程完全一致。因此，我们可以用动态规划来解决斐波那契数列问题。以下是 Python 代码示例：
def fibonacci(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[0] = 0
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
n = 10
print(f"The {n}th Fibonacci number is: {fibonacci(n)}")
除了斐波那契数列，动态规划还可以应用于解决其他类似的优化问题，例如路径计数、背包问题等。掌握动态规划的思想，可以帮助我们解决各种复杂的算法问题。
进阶思考与拓展
如果每次可以爬 1 阶、2 阶或 3 阶，如何求解？
在原始的攀登楼梯问题中，我们每次只能爬 1 阶或 2 阶。如果我们将问题扩展为每次可以爬 1 阶、2 阶或 3 阶，那么状态转移方程应该如何改变？
在这种情况下，爬到第 i 阶楼梯的方法数等于爬到第 i-1 阶的方法数、爬到第 i-2 阶的方法数和爬到第 i-3 阶的方法数之和。因此，状态转移方程变为：
- dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
同时，我们需要更新边界条件：
- dp[0] = 1
- dp[1] = 1
- dp[2] = dp[1] + dp[0] = 2
有了新的状态转移方程和边界条件，我们就可以用动态规划来解决扩展后的问题。以下是 Python 代码示例：
def climbStairsExtended(n):
if n <= 2:
return n if n >= 0 else 0
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1
dp[2] = 2
for i in range(3, n + 1):
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
return dp[n]
n = 5
print(f"Number of ways to climb {n} stairs (1, 2, or 3 steps): {climbStairsExtended(n)}")
通过这个扩展问题，我们可以看到动态规划的灵活性和可扩展性。只需要根据问题的具体情况修改状态转移方程和边界条件，就可以用动态规划来解决各种类似的优化问题。
优缺点分析
? Pros高效解决优化问题
避免重复计算
代码实现简洁
? Cons需要满足最优子结构性质
需要定义状态转移方程
空间复杂度可能较高
常见问题解答
动态规划和递归有什么区别？
动态规划和递归都是将一个大问题分解成若干个子问题来求解。但是，动态规划会保存子问题的解，避免重复计算，从而提高效率。而递归则会重复计算子问题，导致效率较低。 递归： 自顶向下，重复计算子问题。 动态规划： 自底向上，保存子问题的解，避免重复计算。
动态规划有哪些适用场景？
动态规划适用于具有重叠子问题和最优子结构性质的优化问题。 重叠子问题： 问题可以分解成若干个相同的子问题。 最优子结构： 问题的最优解包含子问题的最优解。
如何判断一个问题是否适合用动态规划解决？
可以从以下几个方面来判断一个问题是否适合用动态规划解决： 问题是否具有重叠子问题？ 问题是否具有最优子结构？ 问题是否可以分解成若干个子问题？ 子问题是否可以独立求解？ 如果以上条件都满足，那么这个问题就适合用动态规划解决。
相关问题
除了攀登楼梯问题，还有哪些经典的动态规划问题？
除了攀登楼梯问题，还有很多经典的动态规划问题，例如： 背包问题： 给定一个背包，容量为 C，以及 n 个物品，每个物品有重量 w 和价值 v。求如何选择物品，使得在不超过背包容量的情况下，物品的总价值最大。 最长公共子序列（LCS）： 给定两个字符串，求它们的最长公共子序列的长度。 最长递增子序列（LIS）： 给定一个序列，求它的最长递增子序列的长度。 编辑距离： 给定两个字符串，求将一个字符串转换成另一个字符串所需要的最少操作数（插入、删除、替换）。 矩阵链乘法： 给定 n 个矩阵，求如何安排矩阵的乘法顺序，使得计算量最小。 这些问题都是动态规划的经典案例，掌握这些问题的解法可以帮助我们更好地理解动态规划的思想，并提升解决复杂算法问题的能力。动态规划是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的优化方法。 动态规划常常适用于有重叠子问题和最优子结构性质的问题， 动态规划方法所耗时间往往远少于朴素解法。 动态规划算法是对解最优化问题的一种方法、一种思想，而不是某种具体算法。 动态规划实质上是一种分治思想，是一种特殊的递归。 但是，和递归的区别在于，动态规划具有记忆性，通过填写表把所有已经解决的子问题答案纪录下来，在新问题里需要用到的子问题答案，就可以直接利用表中记录的结果加以引用，避免了重复计算，效率更高。凡是满足最优性原理和无后效性原则的问题，均可使用动态规划求解。 那么看到这里，肯定有读者会问，什么是满足最优性原理和满足无后效性原则。 接下来我们来一一介绍： 最优性原理（最优子结构性质） 最优性原理是指“多阶段决策过程的最优决策序列所具有的性质是：不论初始状态和初始决策如何，对于前面决策所造成的某一状态而言，其后各阶段的决策序列必须构成最优策略”。 可以通俗地理解为子问题的局部最优将导致整个问题的全局最优，即问题具有最优子结构的性质。 无后效性原则 无后效性原则是指“某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关” 。 换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。 1. 动态规划问题一般形式就是求最值。 像寻找最长递增子序列、最小编辑距离、背包问题等等， 他们的共性就是要求在一定的约束条件下，求一个最优值。 2. 求解动态规划的核心，就是穷举。 因为要求最值，肯定要把所有可行的答案穷举出来， 然后在其中找最值对吧？ 动态规划存在「重叠子问题」这个性质， 如果暴力穷举，效率必然是很低的， 所以需要「备忘录」或者 DP table 来优化穷举过程， 避免不必要的计算。 而且，动态规划问题一定会具备「最优子结构」， 才能通过子问题的最值得到原问题的最值。 3. 如何穷举？ 动态规划的穷举和我们之前遇到的递归穷举不太一样， 递归穷举是横向展开， 而动态规划的穷举是在 DP table 上斜着/ 顺序/ 倒序 推进，所以更像在「状态转移」。 明确了以上几点，你就能体会到，动态规划的核心思想其实就是穷举求最值， 因为动态规划过程具备了「重叠子问题」和「最优子结构」的性质，所以我们可以使用 DP table 这种结构来优化穷举过程，保证效率， 这就是动态规划的基本框架。 动态规划解题框架 解决动态规划问题，说白了就三步： 1. 定义「状态」： 状态可能是 「背包容量」和「可选择的物品」 根据状态之间的依赖关系，确定状态转移的顺序。 需要初始化 base case （边界条件） 要明确「选择」和「状态转移」 明确了 base case 和 状态转移方程， 按照状态转移的顺序，通过 for 循环 斜着/ 顺序/ 倒序推进 就可以写出解法。 用代码表示： dp[i][j] = 最值 { dp[i-1][j], dp[i][j-1], … } 这种表达其实就是 base case + 状态转移方程。 在计算机中写代码实际上就是在描述给计算机如何使用 base case + 状态转移方程 斜着/ 顺序/ 倒序推进， 进而求出最终解的过程。
