动态规划入门

最优子结构与状态转移

动态规划（DP）通过将问题分解为重叠子问题，用记忆化或递推避免重复计算。核心前提是最优子结构：大问题的最优解可由其子问题的最优解组合得到。

定义状态表示子问题的解，状态转移方程描述状态间的依赖。例如斐波那契：dp[i] = dp[i-1] + dp[i-2]。设计 DP 时，先明确状态含义，再找转移关系，最后确定边界条件。

无后效性要求当前决策不受未来影响，状态只依赖已求解的子问题。满足这两点，问题才适合 DP。

背包问题

0-1 背包：n 件物品，重量 w[i]、价值 v[i]，背包容量 W，每件最多选一次。状态 dp[i][j] 表示前 i 件物品、容量 j 时的最大价值。

转移：不选第 i 件则 dp[i][j] = dp[i-1][j]；选则 dp[i][j] = dp[i-1][j-w[i]] + v[i]。取两者最大值。可滚动数组优化为 O(W) 空间，逆序枚举 j 避免覆盖。

完全背包：每件物品无限件。转移变为 dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i])，从 dp[i][j-w] 转移表示可重复选。一维实现时 j 正序枚举。

解题思路

识别子问题：问题能否分解？子问题是否重叠？

定义状态：用最少维度完整描述子问题。

写转移方程：状态如何由已知状态推导。

确定顺序：按依赖关系确定计算顺序。

优化：空间压缩、状态合并等。

经典题型：最长公共子序列、最长递增子序列、编辑距离、股票买卖等，都遵循上述框架。