动态规划这四个字我第一次在大二刷蓝桥杯的时候被喂了一嘴当时看题解人家说“用DP做”我就以为DP是某种打表技巧照着每道题硬套状态转移结果不是超时就是答案偏一位。后来出去面试Java岗碰到动态规划的题我才意识到这东西不是背模板能过的——你得真的理解状态怎么设计、转移怎么推而且要用Java把这些写干净不能光会画二维表。这篇就把我这两年在Java里写动态规划的经验整理成一份能直接抄作业的总结从线性DP、树形DP到数位DP再聊几个实操中要命的细节适合准备Java校招/社招面试、刷洛谷题单、或者项目里偶尔要自己处理状态压缩的朋友。1. 从一个灵魂拷问开始动态规划到底在算什么1.1 先跳过斐波那契看一道真正会考的题现在很多教程一上来就讲斐波那契数列然后给个dp[i]dp[i-1]dp[i-2]看完你觉得会了一碰真题又麻了。我建议直接把起点放到“最长上升子序列”这道面试常考题上。题目很简单给一个无序数组nums求其中最长的严格上升子序列长度。比如[10,9,2,5,3,7,101,18]答案是4对应[2,3,7,101]。第一次接触你可能会想能不能贪心碰到更大的就加1试一下[1,3,2,4]贪心会得出31、3、4但正确答案也是3好像没问题。可换成[1,3,2,5]贪心选1、3、5长度是3但1、2、5也长3这时还是分不出胜负。真正让贪心失效的是[1,5,2,3,4]贪心一路往大走只能取1、5长度2而正确结果是1、2、3、4长度4。你看只盯着“当前值变大”会错过后面更长的路。所以得换一种思路不纠结整条子序列而是问自己一个更小的问题——以某个位置结尾的最长子序列长度是多少这就是动态规划的核心动作把“求整个数组的结果”拆成“求每个位置的结果”再用递推把答案合成出来。1.2 三要素状态、转移、边界动态规划所有的套路浓缩成三句话状态定义、状态转移方程、边界条件与遍历顺序。状态定义解决的是“dp[i]到底表示什么”。对最长上升子序列dp[i]表示“以nums[i]结尾的最长上升子序列长度”。注意这里的“结尾”两个字是整个定义里最关键的它决定了转移方程的写法。转移方程解决的是“怎么从已知状态推出未知状态”。既然dp[i]要求以i结尾那它的前一个数必然来自前面某个更小的数nums[j]并且这个数要满足nums[j] nums[i]否则不叫上升。于是转移就是遍历所有j i如果nums[j] nums[i]就尝试用dp[j] 1更新dp[i]。写成代码很直白public int lengthOfLIS(int[] nums) { int n nums.length; int[] dp new int[n]; int ans 0; // 边界每个位置本身至少能构成长度为1的子序列 Arrays.fill(dp, 1); for (int i 0; i n; i) { for (int j 0; j i; j) { if (nums[j] nums[i]) { dp[i] Math.max(dp[i], dp[j] 1); } } ans Math.max(ans, dp[i]); } return ans; }边界条件往往是最不起眼但最害人的。这里dp[i]的初始值是1因为单独一个数本身就是长度为1的上升子序列如果你把初始值设成0那么整个数组只有一个元素时答案会变成0直接错。还有一个坑最终答案是dp数组里的最大值不是dp[n-1]因为最长子序列不一定要包含最后一个元素。提示很多新手写DP第一反应是拿一个“结果变量”在转移过程中不断更新而不是最后再扫一遍dp数组。这两种写法都对但“最后扫一遍”能逼着自己想清楚状态定义逻辑更不容易漏。2. 用Java写DP这三个习惯比公式更重要2.1 状态定义要从“题目问什么”反推我见过太多人卡在第一步dp数组到底开几维每个维度代表什么教你一个笨但可靠的方法把题目里的限制条件列出来问的是一维数组的问题dp常常一维问的是二维矩阵、两个字符串、或者背包容量加物品个数的问题dp常常二维问的是树上节点之间的关系那就得树形DP维度变成“节点某种状态”。举例求两个字符串的最长公共子序列。题目给了两个字符串变化参数天然就是“处理到第一个串的第i位”和“处理到第二个串的第j位”所以dp至少是dp[i][j]。再拆一层dp[i][j]表示“text1前i个字符和text2前j个字符的最长公共子序列长度”。这样设计状态是因为题目的输入是两个序列你要同时追踪两个指针的进度多一个序列就要多一个维度。这种“题目给了什么状态就跟着什么走”的经验在绝大多数常规DP题里都适用。碰到异常复杂的题目顶多多加一个维度用来表示“当前阶段的状态”比如后面要讲的树形DP里“这个节点染没染色、选没选中”本质也是把隐藏的决策条件拆出来。2.2 转移方程的来源就两个选还是不选上一步是谁说到底DP的转移只有两大来源。第一是“选还是不选”的分支决策比如背包问题对于当前物品你只有“放进背包”和“不放”两种选择那么dp[i][j]的转移就是这两个分支取最优。第二是“上一步是谁”的枚举比如最长上升子序列dp[i]的前一个位置可以是任何符合条件的j所以要枚举。写成通用的思考公式就是当前状态 前序可能状态 当前决策带来的收益/代价。用“选还是不选”这个思路去套0-1背包问题会非常顺。经典题目有N个物品每个物品重量weight[i]、价值value[i]背包容量W问能装下的最大价值。定义dp[i][j]为“只考虑前i个物品背包容量为j时的最大价值”。转移不选第i个物品dp[i][j] dp[i-1][j]选第i个物品要求j weight[i]此时dp[i][j] dp[i-1][j - weight[i]] value[i]两者取最大值。注意这里为什么是dp[i-1][j-weight[i]]因为你要腾出weight[i]的空间来放新物品并且只能从前i-1个物品的决策结果上叠加不能重复选当前物品。这个“只能从i-1来”是0-1背包和完全背包的根本区别如果写成dp[i][j-weight[i]] value[i]那就是允许同一物品重复使用变成完全背包了。2.3 Java的数组默认值、初始化与遍历顺序的坑写Java DP最容易踩的坑我按踩坑频率给你排个序。第一数组默认值。new int[n][m]会把所有元素初始化为0这看起来方便但很多状态是“负无穷”或“正无穷”语义。比如求最小操作次数时未到达的状态应该是一个大数不应该是0否则转移时会被错误地当作合法状态参与比较。解法是手动Arrays.fill或循环初始化。第二一维还是二维涉及空间换时间。有些题用一维数组就够了比如最长上升子序列有些题必须二维比如最长公共子序列。如果你不确定先按最朴素的方式写二维跑通后再优化空间。不要一上来就想滚动数组容易把自己绕晕。第三遍历顺序。背包问题里这个坑特别经典一维滚动数组做0-1背包时容量必须从大到小遍历而做完全背包时容量必须从小到大遍历。原因是0-1背包需要保证每个物品只选一次从大到小遍历时dp[j-weight[i]]还是上一轮的值也就是还没被当前物品“污染”过完全背包恰恰需要自己被覆盖所以从小到大。这个细节面试官特别爱问你如果能现场解释清楚“为什么方向不同”印象分会高很多。再补一个Java专属的坑如果你用Integer而不是int数组做DP进行大量Math.max和自动拆装箱性能会有明显损耗。刷题和面试手写建议一律用基本类型数组int[]或long[]需要键值对映射用HashMap就好。少用ListInteger当DP容器因为频繁访问会有拆箱开销而且代码又臭又长。3. 从线性DP到树形DP常见的四种模型拆解3.1 线性DP序列问题的通用解法线性DP指的是状态只沿着一条线推进比如数组下标递增、字符串位置递增。最长上升子序列、最长公共子序列、最大子段和都属于这一类。这类题的核心是“位置”这个维度你只要想清楚当前位置和前一个位置或前几个位置的关系就能写出来。拿最大子段和举例给一个数组找连续子数组的最大和。dp[i]定义为“以nums[i]结尾的连续子数组的最大和”。转移只有两个分支要么把nums[i]接到前面的子数组后面要么从nums[i]重新开始。写成代码就是dp[i] Math.max(dp[i-1] nums[i], nums[i])。这题的dp甚至可以省掉只用两个变量滚动更新。我在面试里见过不少人把这题做复杂了堆了一堆前缀和、线段树其实一句话就能说透。上面LIS的解法复杂度是O(n^2)数据量稍大比如n10^5就超时。这时候要用二分优化到O(n log n)。思路不再维护“以i结尾”的dp而是维护一个“长度为len的上升子序列的最小末尾值”的数组tails。遍历每个数在tails里用二分找到第一个大于等于当前数的位置替换掉如果找不到就说明能形成更长的上升子序列追加到末尾。整个数组的长度就是答案。public int lengthOfLISBinary(int[] nums) { int[] tails new int[nums.length]; int len 0; for (int num : nums) { int left 0, right len; while (left right) { int mid (left right) 1; if (tails[mid] num) { left mid 1; } else { right mid; } } tails[left] num; if (left len) len; } return len; }这个二分优化不只是LIS能用理解“最小末尾值”的思路后你会慢慢发现很多“求最长xxx序列”的题目都能套类似思想。面试时候如果写出O(n^2)版本再主动补一句“这道题还有二分优化能把复杂度降到O(n log n)”印象分会明显不一样。3.2 背包模型0-1背包、完全背包与循环方向背包问题是笔试和面试里出现频率最高的一类DP我建议你把它当“公式”背下来但要理解公式的由来。三个关键词物品、容量、价值。每道背包题就是在这三个变量上做文章有的是物品无限用完全背包有的是每个物品只能用一次0-1背包有的是求方案数而不是最大价值有的是加了个“必须装满”的限制。0-1背包的二维转移刚才已经写过大多数场景下我们会直接压缩成一维数组for (int i 0; i n; i) { for (int j W; j weight[i]; j--) { dp[j] Math.max(dp[j], dp[j - weight[i]] value[i]); } }注意内层循环必须从W往weight[i]方向走。我当年刚学的时候老觉得从前往后从后往前无所谓后来写了个测试用例才明白从前往后会让dp[j-weight[i]]提前被当前物品更新等于把“只能选一次”变成“选了又选”。这个错误在结果上常常是差一点不多但就是不对特别难排查。完全背包只需要把内层循环改成从weight[i]到W正向遍历。如果题目要求“恰好装满背包”初始化时要让dp[0]0其余dp[j]设为-infinity用很小的负数代替这样只有从0状态转移过去的方案才是合法的未装满的状态永远不会参与比较。这个方法在“方案数”类题目里也适用非常实用。3.3 树形DP在递归里先dfs孩子再回头算父亲树形DP是我个人觉得最容易“听起来难、做起来有套路”的类型。它和普通DP的区别在于状态定义在一个树的节点上转移方向是从子节点往父节点汇总。典型题型是“树上的最大独立集”在一棵树上选一些节点要求被选节点之间不能有直接父子关系问最多选几个。思路是每个节点只有两种状态选、或者不选。用dp[node][0]表示不选当前节点时以该节点为根的子树能得到的最大值dp[node][1]表示选当前节点的最大值。那么不选当前节点时子节点可以选也可以不选取每个子节点的最大值再累加dp[node][0] sum(max(dp[child][0], dp[child][1]))选当前节点时所有子节点都不能选dp[node][1] 1 sum(dp[child][0])实现上需要先深搜到叶子再在回溯阶段把子节点的dp累加给父节点。Java里通常用邻接表存树用布尔数组标记访问避免走回父节点。public class TreeDp { private ListListInteger graph; private int[][] dp; public int maxIndependentSet(int n, int[][] edges) { graph new ArrayList(); for (int i 0; i n; i) graph.add(new ArrayList()); for (int[] e : edges) { graph.get(e[0]).add(e[1]); graph.get(e[1]).add(e[0]); } dp new int[n 1][2]; dfs(1, 0); return Math.max(dp[1][0], dp[1][1]); } private void dfs(int node, int parent) { dp[node][1] 1; for (int child : graph.get(node)) { if (child parent) continue; dfs(child, node); dp[node][0] Math.max(dp[child][0], dp[child][1]); dp[node][1] dp[child][0]; } } }树形DP还有一个很常见的变体是“树上背包”比如洛谷的“选课”问题每门课有学分但有些课必须先修其他课形成一棵依赖树问你最多能修哪几门课。解法是把子节点当成一组物品在DFS过程中做背包式合并复杂度是O(n*m)而不是O(n*m^2)关键在于合并时对每个子节点只枚举子树大小范围和已处理节点数。这类题目写起来比较绕但套路非常固定先dfs到底再在回溯阶段用临时数组做背包合并最后把临时结果拷回dp数组。4. 数位DP与DP优化的进阶操作4.1 数位DP解决“某个区间内有多少个数满足条件”数位DP是面试中稍有区分度的知识点竞赛题也很爱考。典型问题是求[L, R]区间内有多少个整数其十进制表示中不包含某个数字。直接遍历肯定超时因为区间可能到10^18。数位DP的思路是“按位统计”把一个数字拆成一位一位来决策每一位只有两种状态这一位能不能自由填也就是之前是否已经小于上界。模板一般是记忆化搜索而不是裸的递推。因为数位DP天然的搜索框架很容易记忆化直接用递推反而难写。以“统计不含4的数的个数”为例public long countWithoutFour(long limit) { String s Long.toString(limit); int n s.length(); long[][] memo new long[n][2]; for (long[] row : memo) Arrays.fill(row, -1); return dfs(0, true, s, memo); } private long dfs(int pos, boolean limited, String s, long[][] memo) { if (pos s.length()) return 1; int tight limited ? 1 : 0; if (memo[pos][tight] ! -1) return memo[pos][tight]; long res 0; int maxDigit limited ? s.charAt(pos) - 0 : 9; for (int d 0; d maxDigit; d) { if (d 4) continue; res dfs(pos 1, limited d maxDigit, s, memo); } memo[pos][tight] res; return res; }这个模板里的核心参数是limited它表示“当前位有没有受到上界约束”。一旦某一位已经小于上界后面所有位都可以自由填0到9只要受了约束继续受约束。这样memo[pos][limited]就能缓存“位置相同、受限状态相同”的结果把复杂度从暴力枚举指数级降到O(位数 * 10)。求区间[L, R]时答案就是calc(R) - calc(L-1)这也是个惯用套路。注意数位DP的记忆化搜索里limitedtrue的状态千万不要缓存复用因为不同上界下的受限路径完全不同。要么像上面这样把limited放进缓存维度要么只在limitedfalse时读缓存。这个细节很容易搞错一旦写错你会发现样例能过、大数会挂。4.2 空间优化滚动数组到底在滚什么很多DP题的dp[i]只依赖dp[i-1]你开一个完整的n维数组就是浪费。比如斐波那契类型的状态只需要开两个变量交替保存LCS类型只要两行因为dp[i][j]只依赖dp[i-1][j-1]、dp[i-1][j]、dp[i][j-1]。这里有一个看似简单但特别容易翻车的点如果按行更新并且同一行的结果要被下一行用到你必须保证更新时用的是“上一行的旧值”而不是本行刚刚覆盖的值。最稳的办法是先保留旧行或者直接从后往前更新。我看过很多人写二维滚动数组直接把int[][] dp new int[n][m]改成int[][] dp new int[2][m]然后i % 2取当前行、(i-1) % 2取上一行。这个写法没问题但要注意每次循环开始时当前行的旧数据要不要清空。如果不清空某些没被更新的格子会残留上一轮的值导致转移时引用到脏数据。如果状态定义是“恰好等于某容量”这种就必须清空如果是“最多某容量”且可以用旧值兜底则可以不清空。这也是为什么我建议新手先写完整二维数组跑通后再优化不然排查半天最后发现是滚动数组留下的脏值。4.3 四边形不等式、分治与二分优化什么时候值得学很多人在题单里看到“四边形不等式优化”就慌了觉得是劝退内容。我的建议是面试阶段先弄懂它的使用条件不要在推导上花太多时间竞赛冲刺再深入。四边形不等式的核心场景是区间DP比如石子合并、矩阵链乘状态转移形如dp[i][j] min(dp[i][k] dp[k1][j]) cost(i,j)。如果cost满足“四边形不等式”和“单调性”那么dp[i][j]的最优决策点k是单调的于是可以在转移时把枚举k的范围缩小到[opt[i][j-1], opt[i1][j]]复杂度从O(n^3)降到O(n^2)。这个优化的难点不在枚举而在验证cost区间是否满足性质。实战中我很少手推更多是先用普通区间DP跑一遍如果超时再试探性地套四边形不等式优化用随机数据对拍确认结果没变。分治优化Divide and Conquer DP适用于dp[i][j] min(dp[i-1][k] cost(k1, j))这种“分层转移”形式并且最优决策点也单调。套路是每一层单独做一次分治递归计算mid的最优点然后左右区间的最优点范围跟着收窄。二分优化则在LIS、最长递增子序列这类“找单调位置”的问题里用得最多。说实话这些优化在Java面试里考得很少但如果你写在简历里写了“熟悉动态规划优化”面试官可能会追问所以我建议至少能说出“每个优化解决什么问题、什么时候不能用”这两件事就已经比多数候选人都到位了。5. 面试手撕与刷题实战我的排查经验和技巧5.1 从洛谷题单到蓝桥杯怎么刷才不走弯路如果你是为了准备Java岗位面试我不建议一头扎进洛谷的困难题单。面试里的DP题难度基本集中在“你能设计出二维状态并写对转移”就够用了极少数考到树形DP。所以刷题优先级应该是基础线性DPLIS、LCS、最大子段和→ 0-1背包/完全背包 → 区间DP → 简单树形DP → 数位DP入门。洛谷的“动态规划”题单里有很经典的“过河卒”“采药”“疯狂的采药”这些题分别对应二维DP、0-1背包、完全背包非常适合拿来练手。蓝桥杯的真题则比较偏“数学建模DP”混合比如数字三角形、乘积最大这类做的时候要额外注意“状态维度要不要多开一维记录余数或乘积符号”。我自己的刷法是这样的第一遍不看题解先死磕一小时实在没思路再去看题解的“状态定义”那一段看完后合上题解自己把转移和代码写出来。这个“只看状态定义”的习惯帮了我大忙因为它强制我去理解“为什么这里要这样设计状态”而不是照抄转移方程。第二遍隔一天再做同一道题能做到默写出来这道题才算真正过。5.2 结果对不上样例时的排查顺序写DP调程序最怕的就是样例过不了然后瞎改。我建议你按这个顺序查先查状态定义和转移方程有没有漏分支再查初始化最后查遍历顺序和下标偏移。先看状态定义。比如“最长公共子序列”如果dp[i][j]定义的是“前i个字符”和“前j个字符”那么循环里访问text1.charAt(i-1)而不是text1.charAt(i)因为i表示长度不是下标。这是最常见的越界或错位问题。再看初始化dp[0][j]和dp[i][0]通常都是0但如果你定义的是“以i结尾的LCS”那初始化直接爆炸。最后看遍历顺序背包、区间DP如果方向写反结果往往和答案非常接近比如差个1这种最迷惑人。我有个土办法写完后用一个小数组手动模拟一遍循环把每次dp更新的中间结果写在纸上看一眼基本一眼就能发现方向错在哪。有时候样例能过、提交超时那大概率是状态数太多或者转移枚举范围太大。这时候先看能不能把内层循环剪枝比如背包里j直接从W到weight[i]而不是每次都从W到0再看能不能用贪心排除明显不可能的k比如区间DP里可行决策点范围。如果数据量是n2000O(n^3)是能过的Java跑2000的三次方大约8e9肯定超时通常就要考虑四边形不等式或换思路了。5.3 Java细节溢出、递归深度与输出类型动态规划里很多题目的答案是方案数比如“有多少种路径”这个值会非常大题目一般会告诉你“对10^97取模”。Java里有两个选择用long数组存转移过程中每次取模或者用int加Math.floorMod。我个人建议DP数组直接用long因为乘法取模时long能轻松避免中间溢出如果用int一不小心就爆了。取模的时候注意所有加法都做一次% MOD不要攒到最后再取中间早就溢出成负数了。递归深度是树形DFS和数位DP的老大难。Java默认栈深度一般在一万左右树形DP遇到一条链形的树递归一万层必挂。解决办法有几个第一个是改成迭代DFS用显式栈模拟递归第二个是先用sys.setrecursionlimit这种方式的Java替代方案——抱歉Java没有只有加启动参数-Xss增加栈大小第三个最实用很多树形DP可以改成ListInteger存父节点方向用队列从叶子节点自底向上计算避开递归。我在蓝桥杯现场被链状树坑过一次之后写树形DP都会默认先瞟一眼数据范围超过20000就谨慎递归。5.4 几个独家小技巧建议收藏最后分享几个我踩过几次坑才总结出来的习惯。第一所有DP题先手写状态转移方程再写代码。哪怕面试官催你你也先在注释里把dp[i][j]的含义写一行再写循环。这能防止写着写着把状态定义给忘了。第二初始化时多看一眼“哨兵节点”。很多二维DP需要在数组外面包一圈边界比如棋盘路径问题里dp[0][j]和dp[i][0]的边界值。如果你不特意处理Java默认值0反而可能成为合法路径导致结果偏大。解决方法是把边界设成极大值或极小值或者在循环里跳过边界。第三现场手撕DP时优先写“记忆化搜索”而不是“迭代递推”。不是说迭代不好而是记忆化搜索天然不需要你提前想清楚遍历顺序只要写出搜索函数和状态转移剩下的交给递归和缓存。这对面试场景特别友好因为手写迭代时遍历方向写反了你很难发现。数位DP、树形DP用记忆化搜索尤其明显几乎不用关心“从后往前还是从前往后”。第四对拍测试是个好习惯。自己写一个暴力法bruteForce再随机生成小数据对比暴力结果和DP结果。这个做法在本地IDE里五分钟就能搞定能揪出大量隐藏边界错误。我自己刷洛谷时每次DP题都写一个最笨的暴力解两个答案一对比状态定义错误基本半小时内就能抓出来。这个习惯在面试现场发挥不出来但在平时训练的价值是巨大的。做动态规划这件事入门靠的是把“状态、转移、边界”三件套吃透进阶靠的是大量刷题和调试中积累出来的模式识别。Java这边的语法无非是数组、循环、递归和少量容器操作真正的难点永远在“这题到底该用几维状态、转移方向是什么”上。我的建议是不要怕慢多动手在纸上画状态转移表画上几十张之后看到新题就能直觉地猜出大概的状态设计。祝所有在DP里苦苦挣扎的朋友都能找到那种“看破状态”的爽感。