尚学堂百战程序员之动态规划之个人总结
2026-01-09 14:24:10
动态规划是一种解决复杂问题的方法，通过将问题分解为更小的子问题，并存储子问题的解以避免重复计算，从而高效地找到原问题的解。以下是我对动态规划的个人总结，结合实习招聘中常见的编程题以及背包问题、最长公共子序列/串等经典例子进行阐述。
一、动态规划的应用场景在编程题中，当遇到看似复杂、难以直接求解的问题时，动态规划往往是一个有效的解决方案。特别是当问题具有重叠子问题和最优子结构特性时，动态规划能够显著减少计算量，提高解题效率。
二、动态规划的基本概念- 重叠子问题：原问题可以分解为多个相似的子问题，这些子问题会被重复计算多次。
- 最优子结构：原问题的最优解包含其子问题的最优解。
- 状态转移方程：描述子问题之间关系的数学表达式，用于从已知子问题的解推导出原问题的解。
背包问题是动态规划中的经典问题，包括01背包、完全背包和多重背包等类型。
01背包：每件物品只能拿一次。使用二维数组dp[i][j]表示面对第i件物品，其背包容量剩下j时，能获得的最大价值。状态转移方程为：
dp[i][j] = dp[i-1][j]（当j < c[i]时，拿不了这件物品）
dp[i][j] = max{dp[i-1][j], dp[i-1][j-c[i]]+w[i]}（当j >= c[i]时，比较拿和不拿的两种价值）
完全背包：每件物品可以无限次使用。与01背包的不同在于，第二层循环时j的取值从c[i]到V，状态转移方程与01背包类似，但循环顺序不同。
多重背包：第i件物品有对应的数量。可以转化为01背包问题，添加一层循环来设置物品的数量，状态转移方程为：dp[i][j] = max{dp[i-1][j], dp[i-1][j-k*c[i]]+k*w[i]}。
示例图片：
最长公共子序列：使用二维数组dp[i][j]表示遍历到序列A的第i个字符和序列B的第j个字符的公共序列的最长长度。状态转移方程为：
dp[i][j] = dp[i-1][j-1] + 1（当A[i-1] == B[j-1]时）
dp[i][j] = max{dp[i-1][j], dp[i][j-1]}（当A[i-1] != B[j-1]时）
最长公共子串：与最长公共子序列不同的是，最长公共子串需要连续的子串。当对应元素不同的时候，dp[i][j] = 0。同时还需要一个整数来记录长度，用于比较历史结果和当前的dp长度，更新最大值。
示例图片：
最长回文字串问题也是动态规划的一个经典应用。可以使用二维数组dp[i][j]表示字符串从i到j的子串是否为回文串。状态转移方程为：
- dp[i][j] = true（当i == j时，单个字符是回文串）
- dp[i][j] = dp[i+1][j-1]（当s[i] == s[j]且i+1 < j时，去掉首尾字符后判断剩余子串）
- dp[i][j] = false（其他情况）
在遍历过程中，记录最长的回文字串长度和起始位置。
四、动态规划的解题步骤- 定义状态：明确问题的子结构和状态表示。
- 状态转移方程：根据子问题的关系，推导出状态转移方程。
- 初始化：设置初始状态的值。
- 计算顺序：确定计算子问题的顺序，通常是从小问题到大问题逐步求解。
- 结果输出：根据最终状态的值，得出原问题的解。
动态规划是一种强大的算法设计技术，适用于解决具有重叠子问题和最优子结构特性的问题。通过定义状态、推导状态转移方程、初始化、计算顺序和结果输出等步骤，可以有效地求解复杂问题。在实习招聘中，掌握动态规划的思想和方法，对于提高编程能力和解题效率具有重要意义。
热门标签
