企业官网建设流程全解析

综合算法 I | 动态规划进阶

动态规划进阶

动态规划（Dynamic Programming）是算法中最重要的高级技巧之一。本文总结动态规划的核心概念和经典问题。

动态规划核心

状态定义

明确问题的状态表示，通常是问题的最优子结构。

状态转移

找到状态之间的转移方程，将大问题分解为小问题。

初始条件

确定边界情况和初始状态。

计算顺序

确定状态计算的顺序，确保依赖的状态已计算。

经典问题

0-1 背包问题

def knapsack(weights, values, capacity): n = len(weights) dp = [[0] * (capacity + 1) for _ in range(n + 1)] for i in range(1, n + 1): for j in range(capacity + 1): dp[i][j] = dp[i-1][j] if j >= weights[i-1]: dp[i][j] = max(dp[i][j], dp[i-1][j-weights[i-1]] + values[i-1]) return dp[n][capacity]

最长公共子序列

def longestCommonSubsequence(s1, s2): m, n = len(s1), len(s2) 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] + 1 else: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) return dp[m][n]

编辑距离

def minDistance(word1, word2): m, n = len(word1), len(word2) dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(m + 1): dp[i][0] = i for j in range(n + 1): dp[0][j] = j for i in range(1, m + 1): for j in range(1, n + 1): if word1[i-1] == word2[j-1]: dp[i][j] = dp[i-1][j-1] else: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) return dp[m][n]

动态规划优化

空间优化

将二维 DP 优化为一维，减少空间复杂度。

状态压缩

使用更少的状态表示问题。

总结

动态规划是解决最优化问题的强大工具。掌握核心概念和经典问题，可以解决大量算法问题。