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

综合算法 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 优化为一维减少空间复杂度。状态压缩使用更少的状态表示问题。总结动态规划是解决最优化问题的强大工具。掌握核心概念和经典问题可以解决大量算法问题。