动态规划例题众多详细讲解

动态规划例题众多详细讲解从核心理论到经典实战·由易到难系统掌握DP算法Contents课程目录从动态规划核心理论出发，逐步深入经典题型与进阶实战，系统构建DP解题能力。01DP核心理论与解题框架02一维线性DP经典例题03背包问题深度解析04子序列DP实战讲解05进阶应用与综合实战Chapter01DP核心理论与解题框架掌握最优子结构、重叠子问题与无后效性三大要素ALGORITHMFUNDAMENTALS动态规划三要素动态规划的适用前提是问题同时具备三大特征：最优子结构保证问题可分解、重叠子问题使得记忆化有价值、无后效性确保状态转移的确定性。三者缺一则不适合用DP求解。最优子结构原问题最优解可由子问题最优解组合推导，如最短路径中A→C必经过某中间点B，则A→B也必为最短。判断方法：假设子问题不是最优，能否通过替换得到更优的原问题解？若能则具备最优子结构。可分解重叠子问题递归求解时相同子问题被重复计算多次，如F(5)=F(4)+F(3)，而F(4)中又包含F(3)的计算。解法：用数组或哈希表缓存已计算的子问题结果，将指数级时间复杂度降为多项式级。记忆化无后效性当前状态一旦确定就不再被后续决策修改，未来只依赖当前状态值而不关心如何到达该状态。反例：带约束条件的路径问题中，若后续选择依赖"经过了哪些点"的历史信息，则不满足无后效性。状态独立DynamicProgrammingDP通用解题四步法动态规划解题遵循标准化四步流程：明确状态定义→推导转移方程→初始化边界→确定遍历顺序。四步环环相扣，状态定义是基石，转移方程是核心。01定义状态明确dp[i]或dp[i][j]代表的具体含义，如"到达第i阶的方案数"或"前i个物品容量j时的最大价值"dp[i]·dp[i][j]02状态转移找出当前状态与历史状态的数学关系，如dp[i]=dp[i-1]+dp[i-2]，这是DP的核心公式核心公式03边界初始化确定dp[0]、dp[1]等初始值，边界错误会导致整个递推链崩溃，需结合题意仔细验证dp[0]·dp[1]04遍历顺序根据状态依赖关系决定正向或反向遍历，确保计算dp[i]时所依赖的子状态已计算完毕正向/反向DynamicProgramming常见DP类型全景图动态规划按问题结构可分为六大类型，从一维线性到区间DP难度递进。掌握各类型的特征识别方法，能在遇到新题时快速归类并套用对应解题模板，是DP实战能力的关键。六大DP类型对照表类型识别特征代表题目难度一维线性DP状态仅依赖前一或前两个位置爬楼梯、打家劫舍、最大子数组和⭐⭐二维DP需要两个维度描述状态最长公共子序列、编辑距离、最小路径和⭐⭐⭐背包DP容量限制下的选择优化问题01背包、完全背包、多重背包⭐⭐⭐子序列DP在序列中选取/匹配元素最长递增子序列、最长回文子序列⭐⭐⭐股票DP多状态切换的交易决策买卖股票最佳时机I~VI系列⭐⭐⭐⭐区间DP在连续区间上做最优决策戳气球、石子合并、矩阵连乘⭐⭐⭐⭐六大类型按难度递进，一维线性DP是入门基础，区间DP与股票DP属于进阶挑战CHAPTER02一维线性DP经典例题从爬楼梯到打家劫舍，建立DP递推思维的坚实基础DynamicProgramming·01例题1：爬楼梯（一维DP入门）爬楼梯问题本质是斐波那契数列的变体，当前阶的方案数仅由前两阶决定。这道题完美展示了DP四步法的标准应用：状态定义清晰、转移方程简洁、边界明确、正向遍历即可求解。01状态定义n阶楼梯每次走1或2阶，求登顶总方案数。dp[i]定义为走到第i阶的方案数。02状态转移到达第i阶只能从i-1阶走1步或i-2阶走2步，故dp[i]=dp[i-1]+dp[i-2]03边界条件dp[1]=1（一阶楼梯仅1种走法），dp[2]=2（两种走法：1+1或直接2）04遍历与复杂度从i=3正向遍历到n，每次计算仅依赖前两个已知值。时间O(n)，空间O(n)，可优化至O(1)DynamicProgramming·经典例题例题2：打家劫舍（不相邻选取）打家劫舍的核心在于将"不能相邻选取"的约束转化为状态转移：每间房屋只有"偷"或"不偷"两种决策，偷则跳过前一间取dp[i-2]，不偷则继承dp[i-1]，二者取最大值即为最优解。STEP01题意理解一排房屋各有金额nums[i]，不能偷相邻两间，求最大偷窃金额nums[i]≥0STEP02状态定义dp[i]表示前i间房屋能偷到的最大金额dp[i]STEP03转移方程偷第i间得dp[i-2]+nums[i]，不偷则继承dp[i-1]，取两者最大值max(dp[i-1],dp[i-2]+nums[i])STEP04边界与遍历从i=2正向遍历，初始化前两项后逐步递推至最终结果returndp[n-1]DynamicProgramming·Kadane例题3：最大子数组和（Kadane算法）最大子数组和问题的DP核心在于"延续还是重启"的决策：以nums[i]结尾的最大和，要么延续前面的子数组(dp[i-1]+nums[i])，要么从nums[i]重新开始。01题意理解给定整数数组nums，求连续子数组的最大和，至少包含一个元素。子数组必须是原数组中连续的一段序列。MaxΣ02状态定义dp[i]表示以nums[i]结尾的最大连续子数组和。强调"以i结尾"是关键，这决定了状态转移的方向。dp[i]03转移方程dp[i]=max(dp[i−1]+nums[i],nums[i])，延续前段或从当前位置重启。这是Kadane算法的核心决策点。max()04全局最优答案不是dp[n−1]，而是遍历所有dp[i]取最大值，需在过程中维护全局最大值。单次遍历即可完成。O(n)DynamicProgramming·动态规划例题4：最小花费爬楼梯（进阶变体）最小花费爬楼梯在经典爬楼梯基础上将"计数"变为"求最优值"，核心变化在于状态转移从求和变为取最小值，且需要仔细处理起点和终点的边界条件。01题意理解每阶有花费cost[i]，从第0或第1阶出发，每次走1或2阶，求到达楼顶的最小总花费cost[i]02状态定义dp[i]为到达第i阶并支付cost[i]后的最小累计花费dp[i]03转移方程dp[i]=min(dp[i-1],dp[i-2])+cost[i]，从前两阶中花费较小的那个走过来min(a,b)04特殊边界dp[0]=cost[0]，dp[1]=cost[1]（两阶均可作为起点），最终答案取min(dp[n-1],dp[n-2])min(n-1,n-2)Chapter03背包问题深度解析从01背包到完全背包，彻底掌握容量约束下的最优选择DynamicProgramming例题5：01背包（二维标准解法）01背包的状态转移体现了"选或不选"的二元决策：不选当前物品则继承上一行结果dp[i-1][j]，选则腾出重量空间取dp[i-1][j-w[i]]+v[i]。二者取最大值，且必须引用上一行数据保证每件物品只选一次。01题意背包容量V，n个物品各有重量w[i]和价值v[i]，每件最多选一次，求最大总价值w[i]·v[i]02二维状态dp[i][j]表示考虑前i个物品、剩余容量j时的最大价值dp[i][j]03转移方程不选第i件→dp[i-1][j]；选第i件→dp[i-1][j-w[i]]+v[i]（需j≥w[i]），取maxmax(选,不选)04初始化dp[0][j]=0（不选任何物品价值为0），dp[i][0]=0（容量为0无法装任何物品）dp[0][j]=0SPACEOPTIMIZATION01背包空间优化：二维到一维01背包可从O(nV)空间优化至O(V)，核心是用一维数组dp[j]代替二维表。但容量j必须逆序遍历，确保dp[j-w[i]]引用的是上一轮的旧值，防止同一物品被重复选取。01优化观察dp[i][j]仅依赖dp[i-1]行数据，无需保留全部n行，一维数组dp[j]即可02一维转移方程dp[j]=max(dp[j],dp[j-w[i]]+v[i])，遍历每个物品时更新容量维度03逆序遍历关键j从V递减到w[i]，保证dp[j-w[i]]是i-1轮的旧值，满足"每件物品只选一次"04正序遍历陷阱若正序遍历j，dp[j-w[i]]已被当前物品更新，等价于允许重复选取，退化为完全背包DynamicProgramming例题6：完全背包vs01背包完全背包与01背包的唯一区别在于物品可重复选取：01背包转移引用dp[i-1]（上一轮旧值），完全背包引用dp[i]（当前轮新值）。一维实现时，01背包逆序遍历容量，完全背包正序遍历容量。01Knapsack01背包每件物品最多选一次二维转移dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])引用上一行旧值一维实现容量j从V逆序到w[i]防止同一物品被重复计入逆序V→w[i]CompleteKnapsack完全背包每件物品可选无限次二维转移dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+v[i])引用当前行新值一维实现容量j从w[i]正序到V允许当前物品被多次选取正序w[i]→VDynamicProgramming·UnboundedKnapsack例题7：零钱兑换（完全背包求最小值）零钱兑换将"最少硬币数"转化为完全背包的最小值问题：每种硬币可无限使用，dp[i]=min(dp[i],dp[i-coin]+1)。初始化为不可能的大值是关键技巧。01题意理解硬币面额数组coins，凑总金额amount，求最少硬币数量；无法凑出返回-1→-102状态定义dp[i]表示凑出金额i所需的最少硬币数，完全背包模型中硬币可无限使用dp[i]03转移方程遍历每种硬币c，若c≤i则dp[i]=min(dp[i],dp[i-c]+1)，取所有硬币中的最小值min()04初始化技巧dp数组全部填充为amount+1（不可达大值），仅dp[0]=0，最终dp[amount]>amount则返回-1∞Chapter04子序列DP实战讲解LIS与LCS——序列类DP的两大基石DynamicProgramming·LeetCode300例题8：最长递增子序列LISLIS的DP解法以"以nums[i]结尾"为状态核心，对每个元素向前扫描所有可衔接的更小元素，取最长链+1。O(n²)解法直观清晰，进阶可用贪心+二分优化至O(nlogn)。01题意无序整数数组，求最长严格递增子序列长度（子序列不要求连续）SUBSEQUENCE≠SUBARRAY02状态定义dp[i]表示以nums[i]结尾的最长递增子序列长度，初始值全为1dp[i]≥103转移方程对每个j<i，若nums[j]<nums[i]则dp[i]=max(dp[i],dp[j]+1)，双重循环O(n²)O(n²)04最终答案max(dp[0],dp[1],...,dp[n-1])，不一定在dp[n-1]处取得max(dp[0…n-1])DynamicProgramming·例题09例题9：最长公共子序列LCSLCS是二维DP的标杆题目，状态转移由字符是否匹配决定：匹配则对角线+1，不匹配则取上方和左方的较大值。01两个字符串text1和text2，求最长公共子序列长度（子序列不要求连续）02dp[i][j]表示text1前i个字符与text2前j个字符的LCS长度03字符匹配时：dp[i][j]=dp[i−1][j−1]+1，对角线方向加104字符不匹配时：dp[i][j]=max(dp[i−1][j],dp[i][j−1])，取忽略某一侧的较优结果StateTransition状态转移方程MATCHdp[i][j]=dp[i−1][j−1]+1DIFFdp[i][j]=max(dp[i−1][j],dp[i][j−1])i,j对角线←匹配时+1上方←忽略text1[i]左方←忽略text2[j]动态规划·经典模型例题10：编辑距离（三种操作DP）编辑距离将字符串转换问题转化为三种操作的最优选择：替换对应对角线+1、删除对应上方+1、插入对应左方+1。题意理解word1转换为word2的最少操作数，允许插入、删除、替换三种操作。每种操作消耗一步，求最优解。3Operations状态定义dp[i][j]为word1前i字符转换为word2前j字符的最少操作数。状态维度为两字符串长度。dp[i][j]字符相同dp[i][j]=dp[i-1][j-1]，当前字符匹配，无需额外操作。直接继承左上方状态值。+0Cost字符不同dp[i][j]=1+min(替换,删除,插入)，取三种操作最小值。分别对应左上、上方、左方状态。1+minChapter05进阶应用与综合实战区间DP、网格路径与过河卒——DP思维的综合考验DynamicProgramming·Grid例题11：不同路径（网格DP入门）网格路径计数是二维DP的经典应用场景，每个格子只能从上方或左方到达，路径数等于两个来源之和。11111234136103×4网格示意图·右下角为路径总数边界（首行/首列）递推计算格01题意：m×n网格，机器人从(0,0)到(m-1,n-1)，每步只能向下或向右，求路径总数02状态定义：dp[i][j]为从起点到达格子(i,j)的路径数量03转移方程：dp[i][j]=dp[i-1][j]+dp[i][j-1]，只能从上方或左方到达04边界条件：dp[0][j]=1（第一行只能向右），dp[i][0]=1（第一列只能向下）DYNAMICPROGRAMMING例题12：不同路径II（含障碍物）障碍物网格DP的关键处理：障碍格dp值设为0（不可达），后续格子自然跳过该来源。第一行/列的障碍会阻断后续所有格子，需特殊处理边界连续性。题意m×n网格含障碍物（1表示障碍，0表示空地），求从左上到右下的路径数。机器人每次只能向下或向右移动一步，不能进入障碍格。m×nGrid障碍处理若obstacleGrid[i][j]==1，则dp[i][j]=0，该格子不可达也不贡献路径。此处理保证了障碍格不会成为任何有效路径的一部分。dp=0正常格子dp[i][j]=dp[i-1][j]+dp[i][j-1]，与无障碍版本的状态转移方程完全相同。每个格子的路径数等于上方和左方格子路径数之和。↑+←边界陷阱第一行/列遇到障碍后，其后所有格子dp值均为0，单方向路径被完全阻断。初始化时需逐格检查，遇到障碍即停止后续赋值。路径阻断DynamicProgramming·网格最优值例题13：最小路径和（网格最优值）最小路径和将网格DP从计数转为求最优值，状态转移从加法变为取min后加当前值。同一DP框架通过调整转移函数即可适配计数、求最值等不同目标，体现DP的通用性。01题意m×n非负整数网格，从左上角到右下角，求路径数字之和的最小值。每步只能向右或向下移动。典型应用场景包括物流路径规划、成本最优决策等。02状态定义dp[i][j]为从(0,0)到(i,j)的最小路径和。该状态完整刻画了子问题的最优解结构，为后续递推奠定基础。03转移方程dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j]，从上方和左方取较小者后累加当前格数值，体现最优子结构性质。04边界累加dp[0][0]=grid[0][0]，第一行与第一列逐步累加，只有一条路径可选。边界条件是DP正确性的重要保证。动态规划·算法精讲例题14：过河卒（NOIP经典·含障碍路径）过河卒结合网格递推与障碍规避，核心是标记马的9个控制点为不可达，其余格子按F[i][j]=F[i-1][j]+F[i][j-1]递推。题意理解卒从(0,0)到(n,m)只能向下或向右移动，需避开敌方马所在点C及其8个控制点。(0,0)→(n,m)障碍标记用布尔数组g[i][j]标记马的控制点——马自身加上dx/dy偏移的8个跳跃目标，共9个点。9个控制点递推关系g[i][j]=1时F[i][j]=0（不可达），否则按F[i-1][j]+F[i][j-1]递推累加。F=F↑+F←精度陷阱当n,m≤20时路径数可能超出longint范围，必须使用int64或高精度运算避免溢出。int64Implementation过河卒：代码实现要点过河卒实现需处理三个关键环节：马的控制点标记（8方向偏移+边界检查）、首行首列的单方向递推初始化、以及内部格子的标准二维递推。每一步都需判断是否为禁区。01马的控制点标记—dx={-2,-1,1,2,2,1,-1,-2}，dy={1,2,2,1,-1,-2,-2,-1}存储8个跳跃方向—遍历8方向，检查x+dx[k]∈[0,n]且y+dy[k]∈[0,m]，合法则g[x+dx[k]][y+dy[k]]=true8Directions·BoundaryCheck02递推实现—F[0][0]=1；首列F[i][0]=F[i-1][0]（非禁区时），首行F[0][j]=F[0][j-1]（非禁区时）—内部格子：g[i][j]=false时F[i][j]=F[i-1][j]+F[i][j-1]，否则F[i][j]=0Init+2DRecurrenceIntervalDP例题15：戳气球（区间DP经典）戳气球的精髓在于'反向思考'：不考虑先戳哪个（会导致相邻关系变化），而是考虑最后戳哪个，此时左右边界气球仍存在，收益确定。区间DP按长度从小到大递推，保证子问题先求解。01题意理解n个气球各有值nums[i]，戳破第i个获得nums[i-1]×nums[i]×nums[i+1]硬币，求最大值。收益=三者之积02反向思维dp[i][j]表示开区间(i,j)内气球全部戳破的最大收益，k为最后戳的气球。dp[i][j]定义03转移方程dp[i][j]=max(nums[i]×nums[k]×nums[j]+dp[i][k]+dp[k][j])，k遍历(i,j)。maxoverk04实现细节首尾各加值为1的虚拟气球避免边界判断，区间长度len从2到n+1递增遍历。len:2→n+1DYNAMICPROGRAMMING例题16：买卖股票最佳时机（状态机DP）股票DP用状态机建模：每天维护"持有"和"不持有"两个状态，状态转移覆盖买入、卖出、持有不动三种决策。最多交易一次时，买入状态的转移直接从0开始（而非从之前卖出的利润开始）。PROBLEM题意理解每天价格prices[i]，最多完成一笔交易（一买一卖），求最大利润。STATE状态定义dp[i][0]第i天不持有股票的最大利润dp[i][1]第i天持有股票的最大利润TRANSITION不持有转移dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i])继续空仓，或今天卖出TRANSITION持有转移dp[i][1]=max(dp[i-1][1],-prices[i])继续持有，或今天买入（仅一次交易，直接取-prices[i]）STATETRANSFER股票II：无限次交易vs单次交易无限次交易与单次交易的DP差异仅在买入状态转移：单次交易买入从0扣减（-prices[i]），无限次交易从上次卖出利润扣减（dp[i-1][0]-prices[i]）。一处引用差异决定交易次数约束。ATMOST1TRANSACTION最多一次交易持有转移dp[i][1]=max(dp[i-1][1],-prices[i])买入时本金为0，因为之前不可能有卖出操作。首次买入即从零开始，不存在历史利润可复用。−prices[i]UNLIMITEDTRANSACTIONS无限次交易持有转移dp[i][1]=max(dp[i-1][1],dp[i-1][0]−prices[i])买入时本金为dp[i-1][0]，包含之前所有交易的累计利润，使得多次买卖成为可能。dp[i-1][0]−prices[i]ALGORITHM·DP例题17：最长回文子序列（区间DP）最长回文子序列用区间DP从两端向中间收缩：字符相同则两端同时保留（+2），不同则尝试去掉某一端取较优。遍历顺序需i从大到小、j从小到大，确保子问题先求解。01题意理解给定字符串s，求最长回文子序列长度。子序列不要求连续，但需正读反读相同。02状态定义dp[i][j]表示子串s[i..j]中最长回文子序列的长度。03匹配转移当s[i]==s[j]时，dp[i][j]=dp[i+1][j-1]+2，两端字符匹配同时保留。04不匹配转移当s[i]≠s[j]时，dp[i][j]=max(dp[i+1][j],dp[i][j-1])；i逆序、j正序遍历。动态规划·进