DP 核心三要素状态 dp [i]/dp [i][j]、状态转移、初始化 base case优化方向滚动数组降维、空间压缩首先怎么去判断一个问题是否是dp问题第一步判断题目传达信号最大值、最小值最大子数组、最小硬币、编辑距离、最大价值求方案总数、总共有多少种方法爬楼梯多少种、目标和、零钱兑换多少组合问是否可达、能不能凑出来分割等和子集能否凑成sum/2第二步 检查两个核心性质DP 必要条件最优子结构一个大问题的最优解可以由它子问题的最优解推导出来。大问题最优 ← 子问题最优。例子打家劫舍 n 间房子最大值可以由 n‑1 和 n‑2 的最优结果推出来。如果子问题最优推不出全局最优 → 不能 DP可以考虑贪心。重叠子问题递归分解的时候会反复算一模一样的子问题。暴力会重复计算。比如爬楼梯 f (5)f (4)f (3)f (4)f (3)f (2)f (3) 被算了两次。DP 就是开数组把 f (3) 结果存起来避免重复。如果子问题全部不重复分治例如归并排序不需要 DP。!!! 如果题目是求所有具体方案全部集合记住那是回溯不是dp; dp求的是数量最大最小是否可行不需要输出全部路径for example:有多少种爬楼梯方式 dp✔全部爬楼梯的路径 回溯✔第二步检查两个核心性质DP 必要条件① 最优子结构一个大问题的最优解可以由它子问题的最优解推导出来。大问题最优 ← 子问题最优。例子打家劫舍 n 间房子最大值可以由 n‑1 和 n‑2 的最优结果推出来。如果子问题最优推不出全局最优 → 不能 DP可以考虑贪心。② 重叠子问题递归分解的时候会反复算一模一样的子问题。暴力会重复计算。比如爬楼梯 f (5)f (4)f (3)f (4)f (3)f (2)f (3) 被算了两次。DP 就是开数组把 f (3) 结果存起来避免重复。如果子问题全部不重复分治例如归并排序不需要 DP。第三步看决策每一步有多条选择选 / 不选A/B/C 选择dp 题几乎都存在决策点背包选这个物品 / 不选这个物品LIS要不要把当前元素接到前面某个子序列后面打家劫舍偷当前房子 / 不偷当前房子编辑距离删除、插入、替换三选一如果每一步只有唯一选择没有多个决策大概率贪心。第四步快速排除法适合贪心不适合 DP局部最优可以直接得到全局最优。比如买卖股票 Ⅱ每次能无限交易区间选点。贪心每一步只看当下最好DP要保存所有子问题状态。适合回溯 DFS要求枚举全部具体方案而不是求数量 / 最值。子集、全排列输出所有结果。如果题目改成求子集有多少种那就可以 DP。BFS求最短路径、最少步数无权图BFS 更合适。但是注意有些题 BFS 和 DP 都可以解比如零钱兑换。第五步一套实操判断流程做题脑子里按顺序过拿到题目1看输出求【最大 / 最小 / 方案数 / 是否可行】→ 不是基本排除 DP是继续。2能否拆成规模更小的子问题大问题依赖子问题结果最优子结构→ 不能DP 不可用。3子问题有没有大量重复计算重叠子问题→ 有适合 DP没有考虑分治。4每一步是否存在多个决策选 / 不选多种操作→ 有DP 概率很大。5反例验证贪心能不能直接做如果贪心试几个样例发现出错那几乎确定 DP。举例子对比例 1零钱兑换给定硬币凑 amount 最少硬币。贪心[1,3,4], amount6。贪心选 4113 枚最优是 332 枚。贪心错必须 DP。例 2爬楼梯求多少种方案。求数量拆 f (n)f (n‑1)f (n‑2)大量重复子问题两种决策。DP。例 3最大子数组和求最大子问题是以 i 结尾最大值决策接前面或者重新开始DP。第六步判断出来是 DP 之后下一步怎么思考设计 dp 状态一维dp [i]前 i 个或者以 i 结尾子数组子序列二维dp [i][j]两个序列前 i,j区间 i~j背包 i 物品 j 容量。技巧✅子数组、子序列类尽量定义为以 i 结尾而不是前 i 个。转移会好写很多。写出 base case 初始化。坑最多求 max 初始 0求 min 初始无穷 INF计数题 dp [0]1。根据决策写状态转移方程。把每一种选择写出来 max/min 或者相加确定遍历顺序。背包0‑1 倒序完全正序区间 DP 先枚举区间长度LIS i 从前往后j i。确定最终答案注意是否取 dp 数组最大值还是 dp [n]。具体实战实例DP 题型维度梳理说明一维 DP主要使用一维数组dp[]部分题目原始思考是二维但可以空间压缩优化到一维。二维 DP必须二维数组dp[][]很难压缩成干净一维或者压缩后可读性极差笔试一般直接写二维。⭐可以优化为一维原始状态是二维。树 DP不是一维也不是二维是树上 DP递归维护每个节点两个状态。序号题目原始状态维度可优化备注1 背包系列416 分割等和子集二维物品 × 容量⭐一维 boolean笔试直接写一维494 目标和二维物品 × 容量⭐一维 int0‑1 背包计数j 倒序322 零钱兑换 Ⅰ二维物品 × 金额⭐一维 int完全背包求最小正序518 零钱兑换 Ⅱ二维物品 × 金额⭐一维 int完全背包求组合数正序2 打家劫舍198 打家劫舍 Ⅰ一维 dp [i]前 i 间最大收益⭐O(1)一维还可以两个变量213 打家劫舍 Ⅱ一维复用 Ⅰ 逻辑⭐O(1)环形调用两次一维打家劫舍337 打家劫舍 Ⅲ树 DP无数组每个节点两个状态 {偷不偷}递归不属于 1/2 维数组 DP3 子序列 字符串300 LIS 最长递增子序列一维 dp [i]以 i 结尾长度不可压到常数一维数组O (n²) 版本一维贪心二分是另外算法1143 LCS 最长公共子序列二维 dp [i][j]⭐可压缩一维但可读性差笔试优先写二维72 编辑距离二维 dp [i][j]⭐可压缩一维不推荐笔试写笔试直接二维4 子数组53 最大子数组和一维 dp [i]以 i 结尾⭐O(1)一维 Kadane152 乘积最大子数组一维两个一维数组 maxDp、minDp⭐O(1)一维维护最大、最小两个数组5 爬楼梯70 爬楼梯一维 dp [i]⭐O(1)一维变种 k 步依旧一维6 解码方法 91一维 dp [i]前 i 位方案数⭐O(1)一维字符串 DP7 股票 DP121/122/123/188/309/714 股票系列二维 dp [i][j]i 天j 状态持有 / 不持有⭐可空间压缩j 只有很小常数可压缩变量原始模型二维8 区间 DP516 最长回文子序列二维 dp [i][j] i~j 区间不能压缩一维区间 DP必须二维数组9 正则匹配 10二维 dp [i][j] s 前 ip 前 j很难压缩hard笔试直接二维总结提炼笔试记忆版纯一维 DP爬楼梯打家劫舍 Ⅰ、ⅡLIS(300)最大子数组、乘积最大子数组解码方法 91背包的 4 道题理论原型二维笔试全部写优化后的一维。原生二维 DPLCS 1143编辑距离 72股票 DP原始二维可以压缩变量区间 DP最长回文子序列 516正则匹配 10特殊类型不属于一维 / 二维数组 DP打家劫舍 Ⅲ树 DP递归每个节点维护两个状态值。容易混淆点笔试坑背包原型二维笔试一律写一维版本浪费空间。LCS、编辑距离虽然可以使用一维但代码较为绕笔试的话最好选择二维。区间 DP 一定二维dp[i][j]代表 i 到 j 区间没有一维写法。股票 dp [i][0]、dp [i][1]第二维只有固定 2‑4 个状态不是很大可以压缩几个变量但概念上属于二维 DP 思想。LIS 是一维 dp 数组但是内层还套一层 j 循环数组维度不等于循环层数。数组维度看 dp 数组是几个下标dp[a]一维 /dp[a][b]二维不是看你写几层 for 循环。只和前几个元素有关大多一维两个序列互相匹配s1 s2二维下一章节进行实战practice!!!
DP 动态规划笔试高频总结
DP 核心三要素状态 dp [i]/dp [i][j]、状态转移、初始化 base case优化方向滚动数组降维、空间压缩首先怎么去判断一个问题是否是dp问题第一步判断题目传达信号最大值、最小值最大子数组、最小硬币、编辑距离、最大价值求方案总数、总共有多少种方法爬楼梯多少种、目标和、零钱兑换多少组合问是否可达、能不能凑出来分割等和子集能否凑成sum/2第二步 检查两个核心性质DP 必要条件最优子结构一个大问题的最优解可以由它子问题的最优解推导出来。大问题最优 ← 子问题最优。例子打家劫舍 n 间房子最大值可以由 n‑1 和 n‑2 的最优结果推出来。如果子问题最优推不出全局最优 → 不能 DP可以考虑贪心。重叠子问题递归分解的时候会反复算一模一样的子问题。暴力会重复计算。比如爬楼梯 f (5)f (4)f (3)f (4)f (3)f (2)f (3) 被算了两次。DP 就是开数组把 f (3) 结果存起来避免重复。如果子问题全部不重复分治例如归并排序不需要 DP。!!! 如果题目是求所有具体方案全部集合记住那是回溯不是dp; dp求的是数量最大最小是否可行不需要输出全部路径for example:有多少种爬楼梯方式 dp✔全部爬楼梯的路径 回溯✔第二步检查两个核心性质DP 必要条件① 最优子结构一个大问题的最优解可以由它子问题的最优解推导出来。大问题最优 ← 子问题最优。例子打家劫舍 n 间房子最大值可以由 n‑1 和 n‑2 的最优结果推出来。如果子问题最优推不出全局最优 → 不能 DP可以考虑贪心。② 重叠子问题递归分解的时候会反复算一模一样的子问题。暴力会重复计算。比如爬楼梯 f (5)f (4)f (3)f (4)f (3)f (2)f (3) 被算了两次。DP 就是开数组把 f (3) 结果存起来避免重复。如果子问题全部不重复分治例如归并排序不需要 DP。第三步看决策每一步有多条选择选 / 不选A/B/C 选择dp 题几乎都存在决策点背包选这个物品 / 不选这个物品LIS要不要把当前元素接到前面某个子序列后面打家劫舍偷当前房子 / 不偷当前房子编辑距离删除、插入、替换三选一如果每一步只有唯一选择没有多个决策大概率贪心。第四步快速排除法适合贪心不适合 DP局部最优可以直接得到全局最优。比如买卖股票 Ⅱ每次能无限交易区间选点。贪心每一步只看当下最好DP要保存所有子问题状态。适合回溯 DFS要求枚举全部具体方案而不是求数量 / 最值。子集、全排列输出所有结果。如果题目改成求子集有多少种那就可以 DP。BFS求最短路径、最少步数无权图BFS 更合适。但是注意有些题 BFS 和 DP 都可以解比如零钱兑换。第五步一套实操判断流程做题脑子里按顺序过拿到题目1看输出求【最大 / 最小 / 方案数 / 是否可行】→ 不是基本排除 DP是继续。2能否拆成规模更小的子问题大问题依赖子问题结果最优子结构→ 不能DP 不可用。3子问题有没有大量重复计算重叠子问题→ 有适合 DP没有考虑分治。4每一步是否存在多个决策选 / 不选多种操作→ 有DP 概率很大。5反例验证贪心能不能直接做如果贪心试几个样例发现出错那几乎确定 DP。举例子对比例 1零钱兑换给定硬币凑 amount 最少硬币。贪心[1,3,4], amount6。贪心选 4113 枚最优是 332 枚。贪心错必须 DP。例 2爬楼梯求多少种方案。求数量拆 f (n)f (n‑1)f (n‑2)大量重复子问题两种决策。DP。例 3最大子数组和求最大子问题是以 i 结尾最大值决策接前面或者重新开始DP。第六步判断出来是 DP 之后下一步怎么思考设计 dp 状态一维dp [i]前 i 个或者以 i 结尾子数组子序列二维dp [i][j]两个序列前 i,j区间 i~j背包 i 物品 j 容量。技巧✅子数组、子序列类尽量定义为以 i 结尾而不是前 i 个。转移会好写很多。写出 base case 初始化。坑最多求 max 初始 0求 min 初始无穷 INF计数题 dp [0]1。根据决策写状态转移方程。把每一种选择写出来 max/min 或者相加确定遍历顺序。背包0‑1 倒序完全正序区间 DP 先枚举区间长度LIS i 从前往后j i。确定最终答案注意是否取 dp 数组最大值还是 dp [n]。具体实战实例DP 题型维度梳理说明一维 DP主要使用一维数组dp[]部分题目原始思考是二维但可以空间压缩优化到一维。二维 DP必须二维数组dp[][]很难压缩成干净一维或者压缩后可读性极差笔试一般直接写二维。⭐可以优化为一维原始状态是二维。树 DP不是一维也不是二维是树上 DP递归维护每个节点两个状态。序号题目原始状态维度可优化备注1 背包系列416 分割等和子集二维物品 × 容量⭐一维 boolean笔试直接写一维494 目标和二维物品 × 容量⭐一维 int0‑1 背包计数j 倒序322 零钱兑换 Ⅰ二维物品 × 金额⭐一维 int完全背包求最小正序518 零钱兑换 Ⅱ二维物品 × 金额⭐一维 int完全背包求组合数正序2 打家劫舍198 打家劫舍 Ⅰ一维 dp [i]前 i 间最大收益⭐O(1)一维还可以两个变量213 打家劫舍 Ⅱ一维复用 Ⅰ 逻辑⭐O(1)环形调用两次一维打家劫舍337 打家劫舍 Ⅲ树 DP无数组每个节点两个状态 {偷不偷}递归不属于 1/2 维数组 DP3 子序列 字符串300 LIS 最长递增子序列一维 dp [i]以 i 结尾长度不可压到常数一维数组O (n²) 版本一维贪心二分是另外算法1143 LCS 最长公共子序列二维 dp [i][j]⭐可压缩一维但可读性差笔试优先写二维72 编辑距离二维 dp [i][j]⭐可压缩一维不推荐笔试写笔试直接二维4 子数组53 最大子数组和一维 dp [i]以 i 结尾⭐O(1)一维 Kadane152 乘积最大子数组一维两个一维数组 maxDp、minDp⭐O(1)一维维护最大、最小两个数组5 爬楼梯70 爬楼梯一维 dp [i]⭐O(1)一维变种 k 步依旧一维6 解码方法 91一维 dp [i]前 i 位方案数⭐O(1)一维字符串 DP7 股票 DP121/122/123/188/309/714 股票系列二维 dp [i][j]i 天j 状态持有 / 不持有⭐可空间压缩j 只有很小常数可压缩变量原始模型二维8 区间 DP516 最长回文子序列二维 dp [i][j] i~j 区间不能压缩一维区间 DP必须二维数组9 正则匹配 10二维 dp [i][j] s 前 ip 前 j很难压缩hard笔试直接二维总结提炼笔试记忆版纯一维 DP爬楼梯打家劫舍 Ⅰ、ⅡLIS(300)最大子数组、乘积最大子数组解码方法 91背包的 4 道题理论原型二维笔试全部写优化后的一维。原生二维 DPLCS 1143编辑距离 72股票 DP原始二维可以压缩变量区间 DP最长回文子序列 516正则匹配 10特殊类型不属于一维 / 二维数组 DP打家劫舍 Ⅲ树 DP递归每个节点维护两个状态值。容易混淆点笔试坑背包原型二维笔试一律写一维版本浪费空间。LCS、编辑距离虽然可以使用一维但代码较为绕笔试的话最好选择二维。区间 DP 一定二维dp[i][j]代表 i 到 j 区间没有一维写法。股票 dp [i][0]、dp [i][1]第二维只有固定 2‑4 个状态不是很大可以压缩几个变量但概念上属于二维 DP 思想。LIS 是一维 dp 数组但是内层还套一层 j 循环数组维度不等于循环层数。数组维度看 dp 数组是几个下标dp[a]一维 /dp[a][b]二维不是看你写几层 for 循环。只和前几个元素有关大多一维两个序列互相匹配s1 s2二维下一章节进行实战practice!!!