概述上一篇我们学习了贪心算法核心是局部最优能否推出全局最优。这一篇我们进入动态规划也就是常说的DP。动态规划是很多初学者的难点因为它看起来不像排序、二分那样“有固定套路”而更像是在做一件事把一个问题拆成很多个小问题再把小问题的答案存起来它最适合处理的就是这类问题有重叠子问题有最优子结构需要求最值、方案数、可达性状态之间可以转移典型题包括爬楼梯斐波那契数列打家劫舍最长递增子序列背包问题本篇先不急着上复杂题。我们先把动态规划最核心的四个词讲清楚状态、定义、转移、初始化学完这篇你应该能看懂最基础的 DP 题并能自己写出一维 DP 的标准模板。核心概念动态规划到底是什么动态规划的核心思想是把原问题拆成若干子问题保存子问题答案避免重复计算为什么要保存答案如果你直接用递归去做很多问题会发现同一个子问题被重复算很多次。例如斐波那契数列f(n) f(n - 1) f(n - 2)如果直接递归f(n - 1)和f(n - 2)里又会继续算出很多重叠内容。这就导致大量重复计算。DP 的作用就是已经算过的子问题答案直接记录下来下次不用再算动态规划三要素通常可以这样理解状态我用什么变量表示一个子问题转移当前状态怎么从之前状态推出来初始化最开始的已知答案是什么如果这三件事想清楚了DP 就有了轮廓。DP 的本质是记住子问题答案并用它们推导更大的问题。先从最简单的题开始爬楼梯题目一共有n阶楼梯每次可以爬1阶或2阶问有多少种不同方法爬到第n阶。这是 DP 最经典的入门题之一。先找状态我们定义dp[i] 表示爬到第 i 阶楼梯的方法数这就是状态定义。再找转移到达第i阶楼梯最后一步只有两种可能从i - 1阶爬1步上来从i - 2阶爬2步上来所以dp[i] dp[i - 1] dp[i - 2]再找初始化已知dp[0] 1dp[1] 1这里dp[0] 1的含义是“站在原地有一种方式”。Java 代码实现classSolution{publicintclimbStairs(intn){if(n1){return1;}int[]dpnewint[n1];dp[0]1;dp[1]1;for(inti2;in;i){dp[i]dp[i-1]dp[i-2];}returndp[n];}}空间优化状态压缩因为转移只依赖前两个状态所以不需要整个数组。classSolution{publicintclimbStairs(intn){if(n1){return1;}inta1;intb1;for(inti2;in;i){intcab;ab;bc;}returnb;}}爬楼梯是最基础的一维 DP状态是“到第几阶的方法数”。斐波那契数列最直接的状态转移模型斐波那契数列和爬楼梯几乎是同一个模型。题目通常写成计算第n个斐波那契数。定义f[0] 0 f[1] 1 f[i] f[i - 1] f[i - 2]Java 代码实现classSolution{publicintfib(intn){if(n1){returnn;}inta0;intb1;for(inti2;in;i){intcab;ab;bc;}returnb;}}为什么先学斐波那契因为它把 DP 的核心逻辑暴露得非常清楚状态是什么状态如何转移初始条件是什么它是很多 DP 题的最小模型。斐波那契是 DP 入门最干净的模板状态转移几乎一眼可见。动态规划的标准思考流程做 DP 题时不要先急着写代码。先按下面步骤想第一步定义状态问自己我用什么变量表示一个子问题例如dp[i]表示前i个房子能偷到的最大金额dp[i]表示以第i个数结尾的最长递增子序列长度dp[i][j]表示前i个物品、容量j时的最优值第二步找状态转移问自己当前状态能从哪些以前的状态推出来这一步通常是最关键的。第三步确定初始值问自己最小的子问题答案是什么第四步确定遍历顺序问自己我计算当前状态时依赖的状态是不是都已经算过了如果依赖前面的状态就要先算前面的。第五步思考答案在哪里问自己最终答案是 dp[n]还是 dp 数组里的最大值还是多个状态的综合先定义状态再写转移再填初始化最后确定遍历顺序和答案位置。题型一最简单的一维 DP一维 DP 往往长这样dp[i] 只依赖前面的一个或几个状态常见一维 DP 模板int[]dpnewint[n1];dp[0]baseValue;for(inti1;in;i){dp[i]transition(dp[i-1],dp[i-2],...);}returndp[n];典型场景台阶问题线性最优值计数类问题以位置为状态的问题例子简单计数型递推如果一个状态只依赖前两个状态就可以直接这样写for(inti2;in;i){dp[i]dp[i-1]dp[i-2];}一维 DP 的特点是状态顺着数组推进通常只依赖前面少数几个位置。题型二最大子数组和的状态设计题目给定一个整数数组找出具有最大和的连续子数组。这是后面线性 DP 的经典题这里先提前感受一下状态设计。状态定义定义dp[i] 表示以 nums[i] 结尾的最大子数组和这个定义很关键。它不是“前 i 个数的最大和”而是“以 i 结尾”。为什么这么定义因为当前子数组要么接在前一个子数组后面要么从当前元素重新开始。转移方程dp[i] max(dp[i - 1] nums[i], nums[i])含义是如果前面的和对我有帮助就接上如果前面的和是负数直接从自己重新开始Java 代码实现classSolution{publicintmaxSubArray(int[]nums){intnnums.length;int[]dpnewint[n];dp[0]nums[0];intansdp[0];for(inti1;in;i){dp[i]Math.max(dp[i-1]nums[i],nums[i]);ansMath.max(ans,dp[i]);}returnans;}}为什么答案不是dp[n - 1]因为最大子数组可能结束在任何位置。所以最终答案应该是整个dp数组里的最大值。空间优化状态压缩只依赖前一个状态时可以压缩成两个变量classSolution{publicintmaxSubArray(int[]nums){intcurnums[0];intansnums[0];for(inti1;inums.length;i){curMath.max(curnums[i],nums[i]);ansMath.max(ans,cur);}returnans;}}状态一旦定义成“以当前位置结尾”转移就会非常自然。题型三打家劫舍的基础模型题目一排房子每个房子里有一定金额不能偷相邻房子求能偷到的最大金额。这是线性 DP 的经典题。状态定义定义dp[i] 表示前 i 个房子能偷到的最大金额状态转移对第i个房子有两种选择不偷第i个房子dp[i - 1]偷第i个房子dp[i - 2] nums[i]所以dp[i] max(dp[i - 1], dp[i - 2] nums[i])Java 代码实现classSolution{publicintrob(int[]nums){intnnums.length;if(n1){returnnums[0];}int[]dpnewint[n];dp[0]nums[0];dp[1]Math.max(nums[0],nums[1]);for(inti2;in;i){dp[i]Math.max(dp[i-1],dp[i-2]nums[i]);}returndp[n-1];}}为什么这题适合 DP因为当前房子是否能偷取决于前一个房子偷没偷。这正是“状态之间存在依赖”的典型情况。线性 DP 的关键是定义“前 i 个位置”的最优值并用“偷与不偷”推状态。题型四DP 题的遍历顺序很多人写 DP 时状态和转移都想出来了但代码还是错。常见原因是遍历顺序不对一维 DP 一般怎么遍历如果dp[i]依赖dp[i - 1]或dp[i - 2]那么通常要从小到大遍历。例如for(inti2;in;i){dp[i]dp[i-1]dp[i-2];}为什么不能乱序因为你在计算dp[i]时依赖的前置状态必须已经算出来。如果依赖还没准备好结果就不可信。一个简单记法依赖谁就先算谁DP 不是随便循环必须保证当前状态依赖的状态已经提前算完。常见坑点动态规划最容易错在哪里1. 状态定义不清楚很多 DP 错误不是转移错而是状态一开始就定义偏了。状态定义必须清楚回答dp[i] 到底表示什么2. 状态定义太大或太小如果状态定义太粗转移会丢信息。如果状态定义太细复杂度会爆炸。3. 初始化漏掉边界DP 很多错都出在dp[0]dp[1]空数组单元素数组4. 遍历顺序不匹配转移如果当前状态依赖前面的状态就必须先算前面。5. 把“前 i 个”写成“以 i 结尾”这两个状态差别很大。例如最大子数组和里如果你定义成“前 i 个的最大和”转移就会很难写。定义成“以 i 结尾”就自然很多。6. 忘记最终答案不一定在dp[n]有些题答案是dp[n]有些题答案是max(dp)还有些题答案是多个状态取最优。复杂度分析DP 的代价从哪里来动态规划通常把原本指数级的重复递归降成多项式级别。爬楼梯时间复杂度O(n)空间复杂度O(n)可优化到O(1)斐波那契时间复杂度O(n)空间复杂度O(1)最大子数组和时间复杂度O(n)空间复杂度O(n)可优化到O(1)打家劫舍时间复杂度O(n)空间复杂度O(n)可优化到O(1)DP 的关键不只是快而是把重复子问题变成一次计算模板总结最基础的一维 DP 怎么写可以先记住这个通用框架// 1. 定义 dpint[]dpnewint[n1];// 2. 初始化dp[0]baseValue;// 3. 状态转移for(inti1;in;i){dp[i]transition(dp[i-1],dp[i-2],...);}// 4. 返回答案returndp[n];如果只能记一句先定义 dp[i] 的含义再想它怎么由前面的状态推出来总结动态规划是算法里最重要的体系之一。它不是死记硬背公式而是先把问题拆成可重复利用的小问题。你可以重点记住下面几句话DP 的本质是保存子问题答案避免重复计算最重要的四件事是状态、转移、初始化、遍历顺序爬楼梯和斐波那契是最基础的一维 DP最大子数组和要把状态定义成“以当前位置结尾”打家劫舍体现了“选与不选”的典型状态转移写 DP 前一定先说清dp[i]表示什么DP 题最常见的错误是状态定义不清和初始化遗漏