动态规划（Dynamic Programming，简称 DP）是解决优化问题的常用算法之一。它通过将复杂问题分解为更小的子问题，并存储这些子问题的解，从而避免重复计算，提高效率。
动态规划的基本思想
动态规划的核心思想是将复杂问题分解为若干个相互重叠的子问题，并按照一定的顺序求解子问题，最终得到原问题的解。
动态规划的步骤
- 定义状态：将问题分解为若干个子问题，并定义每个子问题的状态。
- 状态转移方程：根据子问题的状态，推导出状态转移方程。
- 边界条件：确定递归的基本情况，即递归的终止条件。
- 计算顺序：确定子问题的计算顺序，确保每个子问题只计算一次。
- 存储结果：将子问题的解存储起来，避免重复计算。
动态规划的应用
动态规划广泛应用于各种领域，如：
- 最长公共子序列
- 最长递增子序列
- 最短路径
- 背包问题
示例：最长公共子序列
假设有两个字符串 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]
更多关于动态规划的内容，请访问本站算法入门教程。