动态规划（Dynamic Programming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。它是一种高效解决优化问题的算法思想，通过保存已解决的子问题的解来避免重复计算，从而提高算法的效率。
动态规划的基本思想
动态规划的核心思想是将复杂问题分解为若干个相互重叠的子问题，然后递归地求解这些子问题。动态规划通常涉及以下三个步骤：
- 最优子结构：一个问题的最优解包含其子问题的最优解。
- 重叠子问题：不同的问题计算中包含了相同的子问题。
- 无后效性：一旦某个给定子问题的解被确定，它就不会被改变。
动态规划的应用场景
动态规划适用于解决具有以下特点的问题：
- 最优子结构：问题的最优解包含其子问题的最优解。
- 子问题重叠：不同的问题计算中包含了相同的子问题。
- 无后效性：子问题的解只依赖于其本身。
实战案例解析
案例一：斐波那契数列
斐波那契数列是动态规划的一个经典案例。给定一个整数n，返回斐波那契数列的第n项。
def fib(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
案例二：最长公共子序列
给定两个字符串str1和str2，找出它们的最长公共子序列。
def longest_common_subsequence(str1, str2):
m, n = len(str1), len(str2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if str1[i - 1] == str2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
案例三：背包问题
给定一个背包容量为W，n件物品，每件物品有价值和重量，求在不超过背包容量的情况下，如何选择物品使得总价值最大。
def knapsack(W, weights, values, n):
dp = [[0] * (W + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(1, W + 1):
if weights[i - 1] <= w:
dp[i][w] = max(values[i - 1] + dp[i - 1][w - weights[i - 1]], dp[i - 1][w])
else:
dp[i][w] = dp[i - 1][w]
return dp[n][W]
总结
动态规划是一种强大的算法思想，通过解决子问题来构建原问题的解。在实际应用中，动态规划可以解决许多复杂问题，如背包问题、最长公共子序列等。掌握动态规划，可以帮助我们更好地破解复杂问题。