深入浅出理解动态规划
在解决问题的过程中，我们常常会遇到一些复杂的场景，比如计算从起点到终点的最短路径、找出最长的公共子序列等。这些问题如果用常规的暴力解法，往往会因为计算量过大而难以实现。而动态规划，就像一位聪明的解题高手，能帮助我们高效地解决这类问题。
动态规划是一种通过把原问题分解为相对简单的子问题，再利用子问题的解来求解原问题的方法。它的核心思想是避免重复计算，将已经计算过的子问题的结果存储起来，在需要的时候直接调用，从而大大提高解题效率。
我们可以从一个生活中的例子来理解动态规划的思路。比如你要爬上一段有 n 级台阶的楼梯，每次只能爬 1 级或 2 级台阶，问有多少种不同的爬法？
如果我们用暴力解法，会不断地尝试各种爬楼梯的组合，这显然会有很多重复的计算。而用动态规划的思路，我们可以这样思考：爬上第 n 级台阶的方法数，等于爬上第 n-1 级台阶的方法数加上爬上第 n-2 级台阶的方法数。因为爬上第 n-1 级台阶后，再爬 1 级就到第 n 级了；爬上第 n-2 级台阶后，再爬 2 级也能到第 n 级。
我们用 f (n) 表示爬上 n 级台阶的方法数，那么就有 f (n) = f (n-1) + f (n-2)。这就是这个问题的状态转移方程，它描述了子问题之间的关系。而当 n=1 时，f (1)=1；当 n=2 时，f (2)=2，这就是问题的边界条件。
下面我们用代码来实现这个爬楼梯问题的动态规划解法：
def climb_stairs(n):if n == 1:return 1if n == 2:return 2# 创建一个数组来存储子问题的解dp = [0] * (n + 1)dp[1] = 1dp[2] = 2# 从3开始计算，直到nfor i in range(3, n + 1):dp[i] = dp[i - 1] + dp[i - 2]return dp[n]# 测试
print(climb_stairs(5)) # 输出8在这段代码中，我们创建了一个 dp 数组来存储爬上每一级台阶的方法数。通过循环计算，我们利用前面已经计算出的结果，逐步得到最终的答案，避免了大量的重复计算。
再来看一个经典的动态规划问题 —— 斐波那契数列。斐波那契数列的定义是：f (0)=0，f (1)=1，f (n)=f (n-1)+f (n-2)（n≥2）。
用动态规划求解斐波那契数列的代码如下：
def fibonacci(n):if n == 0:return 0if n == 1:return 1dp = [0] * (n + 1)dp[0] = 0dp[1] = 1for i in range(2, n + 1):dp[i] = dp[i - 1] + dp[i - 2]return dp[n]# 测试
print(fibonacci(6)) # 输出8从这两个例子可以看出，动态规划的关键在于找到状态转移方程和边界条件，然后通过存储子问题的解来高效地求解原问题。
当然，动态规划的应用远不止这些，它在最长公共子序列、背包问题等众多领域都有着广泛的应用。只要我们掌握了其核心思想，就能在面对复杂问题时，找到高效的解决方案。
更多动态规划示例解析
除了爬楼梯和斐波那契数列，动态规划在许多经典问题中都有精彩应用。下面再通过两个典型案例深入理解其解题逻辑。
一、最长公共子序列（LCS）
最长公共子序列问题是指：给定两个字符串，找出它们中最长的公共子序列（子序列是指不要求连续但顺序一致的字符序列）。
例如字符串 s1 = "abcde" 和 s2 = "ace"，其最长公共子序列是 "ace"，长度为 3。
动态规划解题思路：
- 定义状态：设 dp[i][j] 表示 s1[0..i-1] 和 s2[0..j-1] 的最长公共子序列长度
- 状态转移方程：
- 若 s1[i-1] == s2[j-1]，则 dp[i][j] = dp[i-1][j-1] + 1
- 否则 dp[i][j] = max(dp[i-1][j], dp[i][j-1])
- 边界条件：当 i=0 或 j=0 时，dp[i][j] = 0
代码实现：
def longest_common_subsequence(s1, s2):m, n = len(s1), len(s2)# 创建(m+1)x(n+1)的二维数组dp = [[0]*(n+1) for _ in range(m+1)]for i in range(1, m+1):for j in range(1, n+1):if s1[i-1] == s2[j-1]:dp[i][j] = dp[i-1][j-1] + 1else:dp[i][j] = max(dp[i-1][j], dp[i][j-1])return dp[m][n]# 测试
print(longest_common_subsequence("abcde", "ace")) # 输出3
print(longest_common_subsequence("abc", "def")) # 输出0二、0-1 背包问题
有 n 件物品和一个容量为 w 的背包，每件物品有重量和价值，且每种物品只能选一次。求在不超过背包容量的情况下，能获得的最大价值。
例如：物品重量 [2,3,4,5]，价值 [3,4,5,6]，背包容量 8，最大价值为 9（选择重量 2+3，价值 3+6）。
动态规划解题思路：
- 定义状态：dp[i][j] 表示前 i 件物品放入容量为 j 的背包的最大价值
- 状态转移方程：
- 若物品 i 不放入背包：dp[i][j] = dp[i-1][j]
- 若物品 i 放入背包（需满足重量≤容量）：dp[i][j] = dp[i-1][j-weight[i]] + value[i]
- 取两者最大值：dp[i][j] = max(不放入, 放入)
- 边界条件：dp[0][j] = 0（无物品时价值为 0）
代码实现：
def knapsack(weights, values, capacity):n = len(weights)# 创建(n+1)x(capacity+1)的二维数组dp = [[0]*(capacity+1) for _ in range(n+1)]for i in range(1, n+1):for j in range(1, capacity+1):# 物品i的重量（索引从0开始）weight = weights[i-1]value = values[i-1]if weight > j:# 物品超重，无法放入dp[i][j] = dp[i-1][j]else:# 选择放入或不放入的最大值dp[i][j] = max(dp[i-1][j], # 不放入dp[i-1][j-weight] + value # 放入)return dp[n][capacity]# 测试
weights = [2,3,4,5]
values = [3,4,5,6]
print(knapsack(weights, values, 8)) # 输出9这些例子展示了动态规划从一维到二维的扩展应用。核心依然是：用状态定义子问题，用转移方程建立关联，用存储避免重复计算。