文章目录一、什么是动态规划✨核心三要素二、线性 DP最基础的 DP 形态典型题目 1最大子数组和LeetCode 53典型题目 2最长递增子序列LeetCode 300三、二维 DP拓展到平面与网格典型题目 1不同路径LeetCode 62典型题目 2三角形最小路径和LeetCode 120四、01 背包 DP经典的资源分配问题问题模型思路与状态转移典型题目 1目标和LeetCode 494典型题目 2分割等和子集LeetCode 416五、完全背包 DP物品可重复选择♻️核心差异典型题目 1零钱兑换 IILeetCode 518典型题目 2零钱兑换LeetCode 322六、DP 解题通用步骤总结七、学习路径建议八、QA 互动环节❓一、什么是动态规划✨动态规划是一种将复杂问题拆解为子问题、通过记录子问题解避免重复计算的算法思想核心是状态定义 状态转移 边界条件。核心三要素最优子结构问题的最优解由子问题的最优解推导而来重叠子问题子问题会被重复计算用数组 / 表格记录结果避免重复无后效性当前状态只依赖于之前的状态与未来状态无关二、线性 DP最基础的 DP 形态线性 DP 的状态通常定义在一维数组上状态转移沿线性顺序从左到右 / 从右到左进行。典型题目 1最大子数组和LeetCode 53思路状态定义dp[i]表示以nums[i]结尾的最大子数组和状态转移dp[i] max(nums[i], dp[i-1] nums[i])要么从当前元素重新开始要么接在之前子数组后边界条件dp[0] nums[0]结果max(dp)intdp[100000];intmaxSubArray(int*nums,intnumsSize){dp[0]nums[0];intmaxdp[0];for(inti1;inumsSize;i){dp[i]dp[i-1]nums[i]nums[i]?dp[i-1]nums[i]:nums[i];if(maxdp[i])maxdp[i];}returnmax;}典型题目 2最长递增子序列LeetCode 300思路状态定义dp[i]表示以nums[i]结尾的最长递增子序列长度状态转移dp[i] max(dp[j] 1)其中j i且nums[j] nums[i]边界条件dp[i] 1每个元素自身是长度为 1 的子序列结果max(dp)intlengthOfLIS(int*nums,intnumsSize){intdp[numsSize];dp[0]1;if(numsSize1)return1;for(inti1;inumsSize;i){intmax-10000;intt1;for(intj0;ji;j){if(dp[j]maxnums[j]nums[i]){t0;maxdp[j];}}if(t){dp[i]1;}else{dp[i]max1;}}intmaxdp[0];for(inti1;inumsSize;i){if(dp[i]max)maxdp[i];}returnmax;}三、二维 DP拓展到平面与网格二维 DP 的状态定义在二维数组上常用于解决路径、矩阵、字符串匹配等问题。典型题目 1不同路径LeetCode 62思路状态定义dp[i][j]表示到达(i,j)的路径数状态转移dp[i][j] dp[i-1][j] dp[i][j-1]从上方或左方过来边界条件dp[0][j] 1、dp[i][0] 1第一行 / 列只有 1 条路径intuniquePaths(intm,intn){intdp[m][n];dp[0][0]1;for(intj0;jn;j){dp[0][j]1;}for(inti0;im;i){dp[i][0]1;}for(inti1;im;i){for(intj1;jn;j){dp[i][j]dp[i-1][j]dp[i][j-1];}}returndp[m-1][n-1];}典型题目 2三角形最小路径和LeetCode 120思路状态定义dp[i][j]表示到达第i行第j列的最小路径和状态转移边界元素dp[i][0] dp[i-1][0] triangle[i][0]、dp[i][i] dp[i-1][i-1] triangle[i][i]中间元素dp[i][j] min(dp[i-1][j-1], dp[i-1][j]) triangle[i][j]结果min(dp[m-1][j])最后一行的最小值intminimumTotal(int**triangle,inttriangleSize,int*triangleColSize){intdp[triangleSize][triangleSize];//最小路径和dp[0][0]triangle[0][0];for(inti1;itriangleSize;i){for(intj0;ji;j){if(j0){dp[i][j]dp[i-1][j]triangle[i][j];}elseif(ji){dp[i][j]dp[i-1][j-1]triangle[i][j];}else{dp[i][j](dp[i-1][j]dp[i-1][j-1]?dp[i-1][j-1]:dp[i-1][j])triangle[i][j];}}}intmindp[triangleSize-1][0];for(inti0;itriangleSize;i){if(dp[triangleSize-1][i]min)mindp[triangleSize-1][i];}returnmin;}四、01 背包 DP经典的资源分配问题01 背包问题的核心是每个物品只能选或不选在有限容量下最大化价值。问题模型有n个物品第i个物品重量w[i]价值v[i]背包容量为W求最大可装载价值思路与状态转移状态定义二维版dp[i][j]表示前i个物品、容量j时的最大价值状态转移不选第i个dp[i][j] dp[i-1][j]选第i个容量足够dp[i][j] max(dp[i][j], dp[i-1][j-w[i]] v[i])空间优化一维版逆序遍历容量避免重复选择典型题目 1目标和LeetCode 494转化设正号和为P负号和为N则P - N S且P N sum(nums)得P (sum S)/2问题转化为用数组元素凑出P的方案数01 背包变形。intfindTargetSumWays(int*nums,intnumsSize,inttarget){intsum0;for(inti0;inumsSize;i){sumnums[i];}if((targetsum)%2||abs(target)abs(sum)){return0;}intp(sumtarget)/2;intdp[p1];for(inti0;ip1;i){dp[i]0;}dp[0]1;for(inti0;inumsSize;i){for(intjp;j0;j--){if(jnums[i]){dp[j]dp[j-nums[i]];}}}returndp[p];}典型题目 2分割等和子集LeetCode 416转化数组和为sum若为奇数则直接返回false否则问题转化为是否存在子集和为sum/201 背包可行性问题。boolcanPartition(int*nums,intnumsSize){intsum0;for(inti0;inumsSize;i){sumnums[i];}if(sum%2){returnfalse;}inttargetsum/2;intdp[target1];for(inti0;itarget1;i){dp[i]0;}dp[0]1;for(inti0;inumsSize;i){for(intjtarget;j0;j--){if(jnums[i])dp[j]dp[j-nums[i]]||dp[j];}}returndp[target];}五、完全背包 DP物品可重复选择♻️完全背包与 01 背包的区别是每个物品可以无限次选取。核心差异状态转移与 01 背包一致但容量遍历顺序改为正序允许重复选择典型题目 1零钱兑换 IILeetCode 518思路完全背包求组合数状态定义dp[j]为凑成金额j的组合数转移方程dp[j] dp[j - coin]遍历硬币正序更新金额intchange(intamount,int*coins,intcoinsSize){unsignedlonglongdp[amount1];for(inti0;iamount1;i){dp[i]0;}dp[0]1;for(inti0;icoinsSize;i){for(intj1;jamount;j){if(jcoins[i]){dp[j]dp[j-coins[i]];}}}returndp[amount];}典型题目 2零钱兑换LeetCode 322思路完全背包求最小数状态定义dp[j]为凑成金额j的最少硬币数初始化为无穷大dp[0] 0转移方程dp[j] min(dp[j], dp[j - coin] 1)intcoinChange(int*coins,intcoinsSize,intamount){intdp[amount1];for(inti0;iamount1;i){dp[i]amount1;}dp[0]0;for(inti0;iamount1;i){for(intj0;jcoinsSize;j){if(icoins[j]){dp[i]dp[i]dp[i-coins[j]]1?dp[i-coins[j]]1:dp[i];}}}if(dp[amount]amount){return-1;}else{returndp[amount];}}六、DP 解题通用步骤总结明确问题识别是否满足最优子结构、重叠子问题定义状态用dp[i]/dp[i][j]清晰表达子问题含义推导转移根据问题逻辑写出状态转移方程确定边界初始化最小子问题的解如dp[0]、dp[0][0]计算结果从边界出发递推到最终问题提取答案优化空间可选将二维 DP 降为一维减少内存占用七、学习路径建议先从线性 DP入手理解状态定义与转移的核心逻辑如最大子数组和、LIS再过渡到二维 DP适应多维度状态如路径问题、三角形路径和最后攻克背包系列先掌握 01 背包再拓展到完全背包、多重背包结合已刷过的题目如 53、62、120、198、300、416、494、518可以快速串联知识点形成完整知识网络八、QA 互动环节❓问如何判断一个问题应该用 DP 而不是贪心 / 回溯答贪心只做局部最优选择无法保证全局最优回溯会暴力枚举所有子问题时间复杂度高DP 通过记录子问题解在时间与空间间取得平衡适用于有重叠子问题且需要全局最优的场景。问一维 DP 和二维 DP 如何选择答若问题仅依赖于前一个 / 前几个状态用一维即可若需要记录两个维度的信息如行 列、物品数 容量则需要二维状态。