**题解分析** 1. 状态记录 - a. 确定dp数组的含义 ( 本题可用一维dp,dp[i]表示F(i)的斐波那契数 ) 2. 状态转移 - a. 确定dp的递推公式 ( 递推公式才能够通过已知结果确定后续结果 ) - b. 确定dp的初始化 ( 推动递推公式运行的起点 ) - c. 实现递推公式 ( 有时需要着重注意遍历顺序 ) 3. 结果验证 --- 其实关键就在于，**记录已知状态，通过已知状态确定后续状态。** 关键难点在于，确定递推公式。 --- 基于上述描述，可以看到解法很明显的，只记录了f(n - 1)和f(n - 2)，通过这两个前置结果就可以确定f(n)，所以没必要将所有的状态都记录下来。 这其实也就是**dp压缩的核心思想 —— 只记录需要的状态**。 所以可以归纳出对于明显的动态规划问题的解题步骤： ``` - 能否用动态规划解决； - dp数组记录的状态是什么含义； - dp数组的递推 ( 确定递推公式 初始化dp数组 实现递推 )； - 验证结果的准确性。 ``` ```python class Solution: # 斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。 # 该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是： # F(0) = 0，F(1) = 1 # F(n) = F(n - 1) + F(n - 2)，其中 n > 1 # 给定 n ，请计算 F(n) 。 def fib(self, n: int) -> int: x = 0 y = 1 if n == 0: return x if n == 1: return y for i in range( 2, n + 1 ): z = x + y x = y y = z return y ``` ## 如何确定可以使用动态规划 **个人觉得，可以考虑动态规划的判断方法：** - 结果是否由过去状态的解组成， - 过去状态的解是否同样由过去的过去的解组成， - 并且组成规则是一致的，就可以考虑一下动态规划了。 具体的如下： ``` 如何确定题目是否可以用动态规划 动态规划（Dynamic Programming，DP）的核心思想是： 将一个复杂问题分解为重叠的子问题，通过存储子问题的解来避免重复计算。 ═══════════════════════════════════════════ 一、判断能否用 DP 的四个关键特征 ═══════════════════════════════════════════ 满足以下两个核心特征，通常就可以用 DP： 1. 最优子结构 - 问题的最优解包含其子问题的最优解 - 换句话说：大问题的最优解可以由小问题的最优解推导出来 - 判断方法：看能否通过子问题的最优解"组合"或"推导"出原问题的最优解 2. 重叠子问题 - 在求解过程中，同一个子问题会被多次遇到 - 如果没有重叠子问题（像分治法那样子问题互不重叠）， 通常用递归即可，不需要 DP - 判断方法：画出递归树，看是否有相同的节点被重复计算 此外，还有两个辅助特征： 3. 无后效性 - 某个状态一旦确定，后续的决策不受之前如何到达该状态的影响 - 即"过去只通过状态影响未来，而不直接参与未来决策" - 这是构造 dp 数组和状态转移方程的前提 4. 状态可量化 - 能够定义出清晰的状态表示（通常是一维或多维数组） - 能够写出状态转移方程 - 数据规模通常在 10^2 到 10^5 之间（太大的话可能需要优化） ═══════════════════════════════════════════ 二、常见的 DP 题目"信号词" ═══════════════════════════════════════════ 看到以下关键词，应优先考虑 DP： - "最长" / "最小" / "最大" / "最少" - "方案数" / "组合数" / "路径数" - "是否存在" / "是否可以" - "子序列" / "子数组" / "子串" （连续的或不连续的） - "编辑距离" / "转换" - "背包" / "选择" ═══════════════════════════════════════════ 三、判断流程 ═══════════════════════════════════════════ Step 1：看数据规模 - n ≤ 20 左右 → 可能是状态压缩 DP 或暴力 - n ≤ 100~500 → 可能是 O(n²) 或 O(n³) 的 DP - n ≤ 10^5 → 可能是 O(n) 或 O(n log n) 的 DP - n ≥ 10^6 → DP 可能需要优化（滚动数组、单调队列优化等） Step 2：看题目类型 - 求最优解（最大/最小） → 极大可能是 DP 或贪心 - 求总数（多少种方案） → 极大可能是 DP - 求是否存在（可行解） → 可能是 DP - 求所有解的具体路径 → 可能是 DP + 回溯重建 Step 3：尝试定义状态 - 能否用 f(i) 表示"考虑到第 i 个位置时的答案"？ - 能否用 f(i, j) 表示"第一个序列处理到 i，第二个处理到 j"？ - 状态维度通常是 1 到 3 维，超过 3 维可能就不是最优解法 Step 4：尝试写出状态转移方程 - 从当前状态出发，可以进行哪些选择/决策？ - 该状态如何从前面的状态推导而来？ - 如果写不出清晰的状态转移方程，可能不适合用 DP Step 5：画递归树检查重叠子问题 - 把问题写成递归形式，画出递归树 - 如果树中出现大量重复的递归调用，就是 DP 的强信号 ═══════════════════════════════════════════ 四、DP 与其他算法的区分 ═══════════════════════════════════════════ DP vs 贪心： DP：需要考虑多种选择，每个阶段有多个可能的决策 贪心：只需做单一选择（局部最优即全局最优） 区分方法：看是否可以通过"反例"推翻贪心策略 DP vs 回溯/DFS： DP：求最优解/计数，数据规模较大 回溯/DFS：求所有具体解/路径，数据规模较小（n ≤ 20） 区分方法：看数据规模和是否要求列出所有解 DP vs 分治： 分治：子问题互不重叠（如归并排序、快速排序） DP：子问题大量重叠 区分方法：画递归树 DP vs 双指针/滑动窗口： 滑动窗口：通常是连续子数组/子串问题，满足某种单调性 DP：子问题更复杂，窗口法无法覆盖所有情况 ═══════════════════════════════════════════ 五、经典 DP 问题速查 ═══════════════════════════════════════════ 1. 线性 DP - 爬楼梯（Climbing Stairs） - 打家劫舍（House Robber） - 最长递增子序列（LIS） - 最大子数组和（Kadane 算法） 2. 序列 DP - 最长公共子序列（LCS） - 编辑距离（Edit Distance） - 正则表达式匹配 - 通配符匹配 3. 背包 DP - 0-1 背包 - 完全背包 - 多重背包 - 分组背包 4. 区间 DP - 石子合并 - 戳气球（Burst Balloons） - 最长回文子序列 - 多边形三角剖分 5. 状态压缩 DP - 旅行商问题（TSP） - 铺砖问题 - 集合覆盖 6. 树形 DP - 树的最大独立集 - 二叉树中的最大路径和 - 树的最长直径 7. 数位 DP - 数字 1 的个数 - 不含连续 1 的非负整数 - 可被 K 整除的整数 ═══════════════════════════════════════════ 六、总结 ═══════════════════════════════════════════ 题目可以尝试用 DP 的充分非必要条件： - 求最值 / 计数 / 是否存在 - 存在重叠子问题（画出递归树验证） - 存在最优子结构 - 问题规模在 DP 可处理范围内 题目不适合用 DP 的信号： - 要求列出所有具体解且 n 很大 - 子问题完全不重叠（分治即可） - 无法定义明确的状态转移 - 贪心可以直接得到最优解且易于证明 如果在做题时不确定，可以先尝试写出暴力递归， 然后观察递归树中是否有重复计算的节点—— 这是判断 DP 是否适用的最直观方法。 ```