星野爱
动态规划（Dynamic Programming，简称 DP）是一种非常重要的算法思想，用于解决具有重叠子问题和最优子结构性质的问题，能大幅优化时间复杂度。下面详细介绍其解题思路和通用框架：
一、解题核心思路
动态规划的核心是拆分问题、利用子问题结果推导原问题，关键在于找到状态转移的规律，核心要点包括：
重叠子问题：问题可分解为多个重复出现的子问题（比如爬楼梯中，计算
dp[5]会用到dp[4]和dp[3]，而dp[4]又依赖dp[3]等 ），避免重复计算子问题是 DP 优化的关键。最优子结构：原问题的最优解包含子问题的最优解（比如最短路径问题中，全局最短路径必然由局部最短路段组成 ），保证能用子问题结果推导原问题。
状态定义：抽象出
dp[i]（或多维dp[i][j]等 ），清晰描述 “当前状态” 对应的子问题，是动态规划的基础。状态转移方程：明确
dp[i]与子问题dp[...（如dp[i-1]、dp[i-2]）的推导关系，这是动态规划的核心逻辑。
二、通用解题框架（以一维 DP 为例）
动态规划解题通常遵循以下步骤，可根据问题复杂度扩展为多维：
1. 定义状态（核心第一步）
根据问题场景，定义 dp[i] 代表的具体含义。
例 1（爬楼梯）：
dp[i]表示爬到第i阶楼梯的方法总数。例 2（最大子数组和）：
dp[i]表示以第i个元素结尾的最大子数组和。
2. 推导状态转移方程
分析 dp[i] 如何由更小的子问题推导而来，写出递推公式。
爬楼梯：
dp[i] = dp[i-1] + dp[i-2]（第i阶可由i-1阶走 1 步，或i-2阶走 2 步到达 ）。最大子数组和：
dp[i] = max(dp[i-1] + nums[i], nums[i])（以i结尾的最大和，要么是 “前面子数组延续”，要么是 “重新以nums[i]开头” ）。
3. 初始化状态（边界条件）
确定最小子问题的结果，为递推提供起点。
爬楼梯：
dp[1] = 1（1 阶只有 1 种走法 ），dp[2] = 2（2 阶有 “1+1” 或 “2” 两种 ）。最大子数组和：
dp[0] = nums[0]（单个元素的子数组和就是自身 ）。
4. 遍历计算（填充 DP 表）
按照状态转移方程，从初始状态开始依次计算 dp[i]，直到覆盖原问题的规模。
爬楼梯按
i从 3 到n遍历；最大子数组和按i从 1 到len(nums)-1遍历。
5. 返回结果（原问题解）
根据状态定义，返回对应 dp 数组中的值。
爬楼梯返回
dp[n]；最大子数组和返回max(dp)（因为dp[i]是 “以i结尾” 的最大和，全局最大需遍历找 ）。
三、动态规划 vs 其他算法
与暴力递归相比，动态规划通过存储子问题结果（避免重复计算），将时间复杂度从指数级（如爬楼梯暴力递归是 \(O(2^n)\) ）优化到多项式级（爬楼梯 DP 是 O(n) ）。
但动态规划也有局限：
空间开销：如果直接用数组存所有子问题，可能占用较多内存（不过多数情况可优化，如爬楼梯用变量滚动优化空间到 \(O(1)\) ）。
状态定义难度：复杂问题（如二维 DP、三维 DP ）的状态抽象和转移方程推导较难，需要大量练习积累。
四、经典案例巩固（二维 DP 示例：最长公共子序列）
问题：给定两个字符串 text1 和 text2，找它们最长公共子序列的长度（子序列不要求连续）。
状态定义：
dp[i][j]表示text1前i个字符、text2前j个字符的最长公共子序列长度。转移方程：
若
text1[i-1] == text2[j-1]（注意字符串索引），则dp[i][j] = dp[i-1][j-1] + 1（公共字符加入子序列 ）。否则，
dp[i][j] = max(dp[i-1][j], dp[i][j-1])（取 “不包含text1[i-1]” 或 “不包含text2[j-1]” 的最大值 ）。
初始化：
dp[0][j] = 0（text1为空时，公共子序列长度为 0 ），dp[i][0] = 0（同理 ）。遍历计算：双重循环遍历
i（1 到len(text1)）和j（1 到len(text2)）。返回结果：
dp[len(text1)][len(text2)]。
掌握动态规划的关键是多练习、多拆解问题，从简单的一维 DP（爬楼梯、斐波那契）入手，再过渡到二维（最长公共子序列、背包问题），逐步理解状态定义和转移的精髓～