文章目录一、算法设计范式概览动态规划 vs 贪心算法二、问题一矩阵连乘问题动态规划经典案例问题描述为什么用动态规划动态规划算法设计1. 状态定义2. 状态转移方程3. 填表过程自底而上4. 结果与回溯5. 复杂度分析关键洞察三、问题二钢条切割问题动态规划简化版问题描述问题特性动态规划算法设计1. 状态定义2. 状态转移方程3. 填表过程n64. 结果5. 复杂度分析与矩阵连乘的对比四、问题三苹果买卖问题贪心算法案例问题描述为什么用贪心算法贪心算法设计1. 核心思路2. 算法伪代码3. 算法执行示例4. 正确性证明5. 复杂度分析与动态规划的对比五、三种问题的算法选择决策树问题特征对比表六、总结算法选择的决策框架核心原则性能对比本文通过三个经典问题——矩阵连乘、钢条切割、苹果买卖深入解析动态规划和贪心算法的核心思想、设计逻辑和应用场景帮助读者掌握这两种重要的算法设计范式。一、算法设计范式概览动态规划 vs 贪心算法共同点都用于解决优化问题都利用最优子结构特性原问题的最优解由子问题的最优解组成都需要将大问题分解为子问题核心区别动态规划需要枚举所有可能的分解情况通过查表避免重复计算通常需要解决所有子问题贪心算法通过贪心选择特性每一步只做局部最优决策不需要枚举所有可能选择原则如果问题满足贪心选择特性局部最优能保证全局最优优先用贪心算法通常更简单高效如果只满足最优子结构但不满足贪心选择特性用动态规划二、问题一矩阵连乘问题动态规划经典案例问题描述给定5个矩阵A、B、C、D、E维度分别为A: 6×11B: 11×7C: 7×15D: 15×3E: 3×21目标找到最优连乘顺序使总乘法次数最少。为什么用动态规划问题特性分析最优子结构如果A₁...Aₙ的最优顺序是(A₁...Aₖ)(Aₖ₊₁...Aₙ)那么两个子序列也必须是各自的最优顺序重叠子问题(A₂A₃A₄)既是(A₂A₃A₄A₅)的子问题也是(A₁A₂A₃A₄)的子问题不满足贪心选择无法通过局部最优直接确定全局最优必须枚举所有切割点穷举法不可行n个矩阵的加括号方式数量是卡塔兰数指数级增长n5时有14种方式n10时有4862种n20时超过10⁹种动态规划算法设计1. 状态定义OPT(i, j) 计算矩阵链AᵢAᵢ₊₁...Aⱼ所需的最少乘法次数2. 状态转移方程OPT(i, j) min{OPT(i, k) OPT(k1, j) pᵢ₋₁pₖpⱼ} (i ≤ k ≤ j-1)逻辑解释任何连乘顺序都可以看作先连乘左边再连乘右边最后合并枚举所有可能的切割点k选择总代价最小的pᵢ₋₁pₖpⱼ是合并两个子矩阵的代价3. 填表过程自底而上维度序列p [6, 11, 7, 15, 3, 21]步骤1初始化OPT[i, i] 0单个矩阵不需要乘法步骤2长度为2的链OPT[1,2] 6×11×7 462OPT[2,3] 11×7×15 1155OPT[3,4] 7×15×3 315OPT[4,5] 15×3×21 945步骤3长度为3的链计算OPT[1,3]矩阵链 A₁A₂A₃切割点 k1(A₁)(A₂A₃)OPT[1,1] OPT[2,3] p₀×p₁×p₃ 0 1155 6×11×15 0 1155 990 2145切割点 k2(A₁A₂)(A₃)OPT[1,2] OPT[3,3] p₀×p₂×p₃ 462 0 6×7×15 462 0 630 1092✓最小OPT[1,3] min{2145, 1092} 1092K[1,3] 2计算OPT[2,4]矩阵链 A₂A₃A₄切割点 k2(A₂)(A₃A₄)OPT[2,2] OPT[3,4] p₁×p₂×p₄ 0 315 11×7×3 0 315 231 546✓最小切割点 k3(A₂A₃)(A₄)OPT[2,3] OPT[4,4] p₁×p₃×p₄ 1155 0 11×15×3 1155 0 495 1650OPT[2,4] min{546, 1650} 546K[2,4] 2计算OPT[3,5]矩阵链 A₃A₄A₅切割点 k3(A₃)(A₄A₅)OPT[3,3] OPT[4,5] p₂×p₃×p₅ 0 945 7×15×21 0 945 2205 3150切割点 k4(A₃A₄)(A₅)OPT[3,4] OPT[5,5] p₂×p₄×p₅ 315 0 7×3×21 315 0 441 756✓最小OPT[3,5] min{3150, 756} 756K[3,5] 4步骤4长度为4的链计算OPT[1,4]矩阵链 A₁A₂A₃A₄切割点 k1(A₁)(A₂A₃A₄)OPT[1,1] OPT[2,4] p₀×p₁×p₄ 0 546 6×11×3 0 546 198 744✓最小切割点 k2(A₁A₂)(A₃A₄)OPT[1,2] OPT[3,4] p₀×p₂×p₄ 462 315 6×7×3 462 315 126 903切割点 k3(A₁A₂A₃)(A₄)OPT[1,3] OPT[4,4] p₀×p₃×p₄ 1092 0 6×15×3 1092 0 270 1362OPT[1,4] min{744, 903, 1362} 744K[1,4] 1计算OPT[2,5]矩阵链 A₂A₃A₄A₅切割点 k2(A₂)(A₃A₄A₅)OPT[2,2] OPT[3,5] p₁×p₂×p₅ 0 756 11×7×21 0 756 1617 2373切割点 k3(A₂A₃)(A₄A₅)OPT[2,3] OPT[4,5] p₁×p₃×p₅ 1155 945 11×15×21 1155 945 3465 5565切割点 k4(A₂A₃A₄)(A₅)OPT[2,4] OPT[5,5] p₁×p₄×p₅ 546 0 11×3×21 546 0 693 1239✓最小OPT[2,5] min{2373, 5565, 1239} 1239K[2,5] 4步骤5长度为5的链最终结果计算OPT[1,5]矩阵链 A₁A₂A₃A₄A₅切割点 k1(A₁)(A₂A₃A₄A₅)OPT[1,1] OPT[2,5] p₀×p₁×p₅ 0 1239 6×11×21 0 1239 1386 2625切割点 k2(A₁A₂)(A₃A₄A₅)OPT[1,2] OPT[3,5] p₀×p₂×p₅ 462 756 6×7×21 462 756 882 2100切割点 k3(A₁A₂A₃)(A₄A₅)OPT[1,3] OPT[4,5] p₀×p₃×p₅ 1092 945 6×15×21 1092 945 1890 3927切割点 k4(A₁A₂A₃A₄)(A₅)OPT[1,4] OPT[5,5] p₀×p₄×p₅ 744 0 6×3×21 744 0 378 1122✓最小OPT[1,5] min{2625, 2100, 3927, 1122} 1122K[1,5] 44. 结果与回溯最优连乘次数1122最优连乘顺序根据K表回溯得到((A(B(CD)))E)验证按此顺序计算C×D7×15×3 315B×(CD)11×7×3 231A×(B(CD))6×11×3 198(A(B(CD)))×E6×3×21 378总计315 231 198 378 1122 ✓5. 复杂度分析时间复杂度O(n³)三重循环空间复杂度O(n²)存储OPT表和K表关键洞察中间结果维度很重要尽量让中间结果维度小后续计算更省自底而上填表确保计算OPT(i, j)时所有子问题都已计算完成枚举所有切割点因为不知道哪个切割点最优必须全部枚举最优子结构全局最优解必须由局部最优解组成三、问题二钢条切割问题动态规划简化版问题描述给定一根长度为n英寸的钢条将其切割成整数长度的段每段可以单独出售。价格表如下长度英寸123456价格元144789目标设计动态规划算法使总收益最大化。问题特性最优子结构长度为n的钢条的最优切割方案包含子段的最优切割方案重叠子问题不同长度的切割方案会共享相同的子问题一维状态状态只依赖长度这一个维度比矩阵连乘更简单动态规划算法设计1. 状态定义r[i] 长度为 i 的钢条的最大收益2. 状态转移方程价格数组定义p[j]表示长度为 j 的钢条段的价格直接出售不切割根据价格表p[1] 1长度为1英寸的钢条价格1元p[2] 4长度为2英寸的钢条价格4元p[3] 4长度为3英寸的钢条价格4元p[4] 7长度为4英寸的钢条价格7元p[5] 8长度为5英寸的钢条价格8元p[6] 9长度为6英寸的钢条价格9元状态转移方程r[i] max{p[j] r[i-j] | 1 ≤ j ≤ i}逻辑解释对于长度为i的钢条枚举第一段的长度j1到i如果第一段长度为j收益为p[j]第一段长度为j直接出售的价格r[i-j]剩余部分长度为i-j的最优切割收益总收益 p[j] r[i-j]选择使总收益最大的j3. 填表过程n6初始化r[0] 0长度为0的钢条收益为0i1长度为1英寸的钢条j1第一段长度为1p[1] r[0] 1 0 1✓唯一选择r[1] 1切割方案不切割整根出售1英寸i2长度为2英寸的钢条j1第一段长度为1p[1] r[1] 1 1 2方案切成11收益 1 1 2j2第一段长度为2p[2] r[0] 4 0 4✓最大方案不切割整根出售2英寸收益 4r[2] max{2, 4} 4最优方案不切割整根出售i3长度为3英寸的钢条j1第一段长度为1p[1] r[2] 1 4 5✓最大方案切成12收益 1 4 5j2第一段长度为2p[2] r[1] 4 1 5✓同样最大方案切成21收益 4 1 5j3第一段长度为3p[3] r[0] 4 0 4方案不切割整根出售3英寸收益 4r[3] max{5, 5, 4} 5最优方案切成12或21i4长度为4英寸的钢条j1第一段长度为1p[1] r[3] 1 5 6方案切成13收益 1 5 6j2第一段长度为2p[2] r[2] 4 4 8✓最大方案切成22收益 4 4 8j3第一段长度为3p[3] r[1] 4 1 5方案切成31收益 4 1 5j4第一段长度为4p[4] r[0] 7 0 7方案不切割整根出售4英寸收益 7r[4] max{6, 8, 5, 7} 8最优方案切成22i5长度为5英寸的钢条j1第一段长度为1p[1] r[4] 1 8 9✓最大方案切成14收益 1 8 9j2第一段长度为2p[2] r[3] 4 5 9✓同样最大方案切成23收益 4 5 9j3第一段长度为3p[3] r[2] 4 4 8方案切成32收益 4 4 8j4第一段长度为4p[4] r[1] 7 1 8方案切成41收益 7 1 8j5第一段长度为5p[5] r[0] 8 0 8方案不切割整根出售5英寸收益 8r[5] max{9, 9, 8, 8, 8} 9最优方案切成14或23i6长度为6英寸的钢条j1第一段长度为1p[1] r[5] 1 9 10方案切成15收益 1 9 10j2第一段长度为2p[2] r[4] 4 8 12✓最大方案切成24进一步24可以优化为222收益 4 8 12j3第一段长度为3p[3] r[3] 4 5 9方案切成33收益 4 5 9j4第一段长度为4p[4] r[2] 7 4 11方案切成42收益 7 4 11j5第一段长度为5p[5] r[1] 8 1 9方案切成51收益 8 1 9j6第一段长度为6p[6] r[0] 9 0 9方案不切割整根出售6英寸收益 9r[6] max{10, 12, 9, 11, 9, 9} 12最优方案切成222三个2英寸段4. 结果最大收益r[6] 12元最优切割方案切成3段每段2英寸2 2 2 65. 复杂度分析时间复杂度O(n²)空间复杂度O(n)与矩阵连乘的对比特性矩阵连乘钢条切割状态维度二维 OPT(i,j)一维 r[i]状态转移枚举切割点k枚举第一段长度j复杂度O(n³)O(n²)难度较复杂较简单四、问题三苹果买卖问题贪心算法案例问题描述一辆卡车从城市A到城市B途经n个苹果市场。在每个市场i可以以价格B[i]买入苹果或以价格S[i]卖出苹果。目标在某个市场i买入在后续市场jj ≥ i卖出使利润 M S[j] - B[i] 最大化。约束卡车只能前进不能后退只能进行一次买入和一次卖出可以在同一市场买入和卖出为什么用贪心算法问题特性分析最优子结构如果(i, j)是最优买卖对那么i一定是1到j之间价格最低的市场贪心选择特性对于每个卖出位置j最优买入位置是j之前包括j价格最低的市场局部最优保证全局最优维护最低买入价格计算每个位置的最大利润与动态规划的区别不需要枚举所有可能的买卖对只需要一次遍历维护最低买入价格复杂度从O(n²)降为O(n)贪心算法设计1. 核心思路对于每个卖出位置j最优买入位置是j之前包括j价格最低的市场。2. 算法伪代码输入B[1..n]每个市场的买入价格数组S[1..n]每个市场的卖出价格数组n市场数量输出optimalBuyMarket最优买入市场编号sellMarket最优卖出市场编号maxProfit最大利润变量说明minBuy到当前位置为止的最低买入价格buyMarket当前最低买入价格对应的市场编号maxProfit到目前为止的最大利润sellMarket当前最大利润对应的卖出市场编号optimalBuyMarket当前最大利润对应的买入市场编号APPLE-TRADING(B, S, n) 1. minBuy ← B[1] // 初始化第一个市场的最低买入价格就是B[1] 2. buyMarket ← 1 // 初始化第一个市场作为当前最低买入价格的市场 3. maxProfit ← S[1] - B[1] // 初始化第一个市场的利润可能为负表示亏损 4. sellMarket ← 1 // 初始化第一个市场作为当前最优卖出市场 5. // 从第二个市场开始遍历 6. for j ← 2 to n // 遍历每个市场j作为潜在的卖出市场 7. do if B[j] minBuy // 如果市场j的买入价格低于当前最低买入价格 8. then minBuy ← B[j] // 更新最低买入价格为B[j] 9. buyMarket ← j // 更新最低买入价格对应的市场为j // 注意这里更新buyMarket但optimalBuyMarket可能不变 // 因为虽然找到了更低的买入价但可能利润不是最大的 10. // 计算在市场j卖出的利润 // 使用当前已知的最低买入价格可能在市场j之前 11. profit ← S[j] - minBuy // 利润 市场j的卖出价格 - 到j为止的最低买入价格 // 这保证了买入市场 ≤ 卖出市场j满足约束条件 12. if profit maxProfit // 如果当前利润大于已知的最大利润 13. then maxProfit ← profit // 更新最大利润 14. sellMarket ← j // 更新最优卖出市场为j 15. optimalBuyMarket ← buyMarket // 更新最优买入市场为当前buyMarket // 注意这里buyMarket是到j为止的最低买入价格对应的市场 // 这保证了(optimalBuyMarket, sellMarket)是最优买卖对 16. 17. return (optimalBuyMarket, sellMarket, maxProfit) // 返回最优买入市场、最优卖出市场和最大利润算法核心逻辑维护最低买入价格第7-9行在遍历过程中始终记录到当前位置为止的最低买入价格及其对应的市场。这是贪心选择的关键——对于每个卖出位置j最优买入位置一定是j之前包括j价格最低的市场。计算当前利润第11行对于每个市场j计算在最低买入价格的市场买入在市场j卖出的利润。这利用了贪心选择特性不需要枚举所有可能的买入位置。更新最优解第12-15行如果当前利润大于已知的最大利润更新最大利润和对应的买卖市场对。为什么这样设计是正确的对于任意卖出位置j如果我们已经知道j之前包括j的最低买入价格是minBuy对应的市场是buyMarket那么(buyMarket, j)就是在j卖出的最优买卖对。因为如果存在更优的买入位置kk j且B[k] minBuy那么算法应该已经在遍历到k时更新了minBuy和buyMarket。因此我们只需要遍历一次对每个卖出位置j用当前已知的最低买入价格计算利润即可。3. 算法执行示例假设输入B [5, 3, 2, 4, 1, 6] // 买入价格S [4, 6, 5, 7, 3, 8] // 卖出价格执行过程详解列说明j当前遍历到的市场编号作为潜在的卖出市场B[j]市场j的买入价格S[j]市场j的卖出价格minBuy到市场j为止的最低买入价格buyMarket当前最低买入价格对应的市场编号profit在市场j卖出的利润 S[j] - minBuymaxProfit到目前为止的最大利润sellMarket当前最大利润对应的卖出市场optimalBuyMarket当前最大利润对应的买入市场逐步执行过程j1初始化处理第一个市场B[1] 5S[1] 4minBuy 5第一个市场最低买入价格就是B[1]buyMarket 1最低买入价格对应的市场profit S[1] - minBuy 4 - 5 -1亏损1元maxProfit -1当前最大利润虽然是亏损sellMarket 1optimalBuyMarket 1含义如果只在市场1买卖会亏损1元j2处理第二个市场B[2] 3S[2] 6更新最低买入价格因为B[2] 3 minBuy 5所以minBuy 3更新为更低的价格buyMarket 2更新为市场2profit S[2] - minBuy 6 - 3 3利润3元更新最大利润因为profit 3 maxProfit -1所以maxProfit 3sellMarket 2最优卖出市场更新为市场2optimalBuyMarket 2最优买入市场更新为市场2含义在市场2买入价格3在市场2卖出价格6利润3元。这是目前最优方案。j3处理第三个市场B[3] 2S[3] 5更新最低买入价格因为B[3] 2 minBuy 3所以minBuy 2更新为更低的价格buyMarket 3更新为市场3profit S[3] - minBuy 5 - 2 3利润3元不更新最大利润因为profit 3 maxProfit 3没有更优sellMarket 2optimalBuyMarket 2保持不变含义虽然找到了更低的买入价格市场3价格2但在市场3卖出的利润3元没有超过当前最优利润3元所以最优方案仍然是市场2市场2。j4处理第四个市场B[4] 4S[4] 7不更新最低买入价格因为B[4] 4 minBuy 2所以minBuy和buyMarket保持不变profit S[4] - minBuy 7 - 2 5利润5元注意这里使用的是市场3的买入价格minBuy2而不是市场4的买入价格更新最大利润因为profit 5 maxProfit 3所以maxProfit 5sellMarket 4最优卖出市场更新为市场4optimalBuyMarket 3最优买入市场更新为市场3即当前的buyMarket含义在市场3买入价格2在市场4卖出价格7利润5元。这是新的最优方案。j5处理第五个市场B[5] 1S[5] 3更新最低买入价格因为B[5] 1 minBuy 2所以minBuy 1更新为更低的价格buyMarket 5更新为市场5profit S[5] - minBuy 3 - 1 2利润2元不更新最大利润因为profit 2 maxProfit 5所以最优方案保持不变sellMarket 4optimalBuyMarket 3保持不变含义虽然找到了更低的买入价格市场5价格1但在市场5卖出的利润2元没有超过当前最优利润5元所以最优方案仍然是市场3市场4。j6处理第六个市场最终结果B[6] 6S[6] 8不更新最低买入价格因为B[6] 6 minBuy 1所以minBuy和buyMarket保持不变profit S[6] - minBuy 8 - 1 7利润7元注意这里使用的是市场5的买入价格minBuy1而不是市场6的买入价格更新最大利润因为profit 7 maxProfit 5所以maxProfit 7sellMarket 6最优卖出市场更新为市场6optimalBuyMarket 5最优买入市场更新为市场5即当前的buyMarket含义在市场5买入价格1在市场6卖出价格8利润7元。这是最终的最优方案。最终结果最优买入市场5价格1元/斤最优卖出市场6价格8元/斤最大利润7元/斤关键洞察minBuy和buyMarket的更新每当遇到更低的买入价格时更新这保证了对于每个卖出位置j我们总是使用j之前包括j的最低买入价格。profit的计算总是使用当前的minBuy计算而不是B[j]这体现了贪心选择特性。最优解的更新只有当profit大于maxProfit时才更新这保证了我们找到的是全局最优解。4. 正确性证明贪心选择特性对于任意卖出位置j最优买入位置一定是j之前包括j价格最低的市场。证明反证法假设存在更优的买入位置kk i且B[k] B[i]其中i是j之前价格最低的市场那么(k, j)的利润 S[j] - B[k] S[j] - B[i] (i, j)的利润但这与i是j之前价格最低的市场矛盾因为如果B[k] B[i]算法应该已经将minBuy更新为B[k]5. 复杂度分析时间复杂度O(n)单次遍历空间复杂度O(1)只使用常数个变量与动态规划的对比如果用动态规划状态定义F[i][j] 在市场i买入、市场j卖出的利润需要计算所有O(n²)个状态复杂度O(n²)贪心算法的优势只需要O(n)时间代码更简单空间复杂度O(1)五、三种问题的算法选择决策树问题是否满足最优子结构 ├─ 否 → 不适合用DP或贪心考虑其他算法 └─ 是 → 是否满足贪心选择特性 ├─ 是 → 优先用贪心算法 │ ├─ 苹果买卖O(n)时间O(1)空间 │ └─ 区间调度无权重O(n log n)时间 └─ 否 → 用动态规划 ├─ 矩阵连乘O(n³)时间O(n²)空间 └─ 钢条切割O(n²)时间O(n)空间问题特征对比表问题算法类型状态维度时间复杂度空间复杂度关键特性矩阵连乘动态规划二维O(n³)O(n²)重叠子问题、最优子结构钢条切割动态规划一维O(n²)O(n)重叠子问题、最优子结构苹果买卖贪心算法无状态表O(n)O(1)贪心选择特性、最优子结构六、总结算法选择的决策框架核心原则先判断最优子结构如果不满足不适合用DP或贪心再判断贪心选择特性如果满足优先用贪心通常更简单高效最后选择动态规划如果只满足最优子结构用DP性能对比算法类型时间复杂度空间复杂度实现难度适用场景贪心算法O(n) 或 O(n log n)O(1) 或 O(n)简单满足贪心选择特性动态规划O(n²) 或 O(n³)O(n) 或 O(n²)中等满足最优子结构 
长河君 · 2026/11/3 18:38:03 · 阅读 1.2k 【计算机算法设计与分析】动态规划与贪心算法教程：从矩阵连乘到资源优化
文章目录一、算法设计范式概览动态规划 vs 贪心算法二、问题一矩阵连乘问题动态规划经典案例问题描述为什么用动态规划动态规划算法设计1. 状态定义2. 状态转移方程3. 填表过程自底而上4. 结果与回溯5. 复杂度分析关键洞察三、问题二钢条切割问题动态规划简化版问题描述问题特性动态规划算法设计1. 状态定义2. 状态转移方程3. 填表过程n64. 结果5. 复杂度分析与矩阵连乘的对比四、问题三苹果买卖问题贪心算法案例问题描述为什么用贪心算法贪心算法设计1. 核心思路2. 算法伪代码3. 算法执行示例4. 正确性证明5. 复杂度分析与动态规划的对比五、三种问题的算法选择决策树问题特征对比表六、总结算法选择的决策框架核心原则性能对比本文通过三个经典问题——矩阵连乘、钢条切割、苹果买卖深入解析动态规划和贪心算法的核心思想、设计逻辑和应用场景帮助读者掌握这两种重要的算法设计范式。一、算法设计范式概览动态规划 vs 贪心算法共同点都用于解决优化问题都利用最优子结构特性原问题的最优解由子问题的最优解组成都需要将大问题分解为子问题核心区别动态规划需要枚举所有可能的分解情况通过查表避免重复计算通常需要解决所有子问题贪心算法通过贪心选择特性每一步只做局部最优决策不需要枚举所有可能选择原则如果问题满足贪心选择特性局部最优能保证全局最优优先用贪心算法通常更简单高效如果只满足最优子结构但不满足贪心选择特性用动态规划二、问题一矩阵连乘问题动态规划经典案例问题描述给定5个矩阵A、B、C、D、E维度分别为A: 6×11B: 11×7C: 7×15D: 15×3E: 3×21目标找到最优连乘顺序使总乘法次数最少。为什么用动态规划问题特性分析最优子结构如果A₁...Aₙ的最优顺序是(A₁...Aₖ)(Aₖ₊₁...Aₙ)那么两个子序列也必须是各自的最优顺序重叠子问题(A₂A₃A₄)既是(A₂A₃A₄A₅)的子问题也是(A₁A₂A₃A₄)的子问题不满足贪心选择无法通过局部最优直接确定全局最优必须枚举所有切割点穷举法不可行n个矩阵的加括号方式数量是卡塔兰数指数级增长n5时有14种方式n10时有4862种n20时超过10⁹种动态规划算法设计1. 状态定义OPT(i, j) 计算矩阵链AᵢAᵢ₊₁...Aⱼ所需的最少乘法次数2. 状态转移方程OPT(i, j) min{OPT(i, k) OPT(k1, j) pᵢ₋₁pₖpⱼ} (i ≤ k ≤ j-1)逻辑解释任何连乘顺序都可以看作先连乘左边再连乘右边最后合并枚举所有可能的切割点k选择总代价最小的pᵢ₋₁pₖpⱼ是合并两个子矩阵的代价3. 填表过程自底而上维度序列p [6, 11, 7, 15, 3, 21]步骤1初始化OPT[i, i] 0单个矩阵不需要乘法步骤2长度为2的链OPT[1,2] 6×11×7 462OPT[2,3] 11×7×15 1155OPT[3,4] 7×15×3 315OPT[4,5] 15×3×21 945步骤3长度为3的链计算OPT[1,3]矩阵链 A₁A₂A₃切割点 k1(A₁)(A₂A₃)OPT[1,1] OPT[2,3] p₀×p₁×p₃ 0 1155 6×11×15 0 1155 990 2145切割点 k2(A₁A₂)(A₃)OPT[1,2] OPT[3,3] p₀×p₂×p₃ 462 0 6×7×15 462 0 630 1092✓最小OPT[1,3] min{2145, 1092} 1092K[1,3] 2计算OPT[2,4]矩阵链 A₂A₃A₄切割点 k2(A₂)(A₃A₄)OPT[2,2] OPT[3,4] p₁×p₂×p₄ 0 315 11×7×3 0 315 231 546✓最小切割点 k3(A₂A₃)(A₄)OPT[2,3] OPT[4,4] p₁×p₃×p₄ 1155 0 11×15×3 1155 0 495 1650OPT[2,4] min{546, 1650} 546K[2,4] 2计算OPT[3,5]矩阵链 A₃A₄A₅切割点 k3(A₃)(A₄A₅)OPT[3,3] OPT[4,5] p₂×p₃×p₅ 0 945 7×15×21 0 945 2205 3150切割点 k4(A₃A₄)(A₅)OPT[3,4] OPT[5,5] p₂×p₄×p₅ 315 0 7×3×21 315 0 441 756✓最小OPT[3,5] min{3150, 756} 756K[3,5] 4步骤4长度为4的链计算OPT[1,4]矩阵链 A₁A₂A₃A₄切割点 k1(A₁)(A₂A₃A₄)OPT[1,1] OPT[2,4] p₀×p₁×p₄ 0 546 6×11×3 0 546 198 744✓最小切割点 k2(A₁A₂)(A₃A₄)OPT[1,2] OPT[3,4] p₀×p₂×p₄ 462 315 6×7×3 462 315 126 903切割点 k3(A₁A₂A₃)(A₄)OPT[1,3] OPT[4,4] p₀×p₃×p₄ 1092 0 6×15×3 1092 0 270 1362OPT[1,4] min{744, 903, 1362} 744K[1,4] 1计算OPT[2,5]矩阵链 A₂A₃A₄A₅切割点 k2(A₂)(A₃A₄A₅)OPT[2,2] OPT[3,5] p₁×p₂×p₅ 0 756 11×7×21 0 756 1617 2373切割点 k3(A₂A₃)(A₄A₅)OPT[2,3] OPT[4,5] p₁×p₃×p₅ 1155 945 11×15×21 1155 945 3465 5565切割点 k4(A₂A₃A₄)(A₅)OPT[2,4] OPT[5,5] p₁×p₄×p₅ 546 0 11×3×21 546 0 693 1239✓最小OPT[2,5] min{2373, 5565, 1239} 1239K[2,5] 4步骤5长度为5的链最终结果计算OPT[1,5]矩阵链 A₁A₂A₃A₄A₅切割点 k1(A₁)(A₂A₃A₄A₅)OPT[1,1] OPT[2,5] p₀×p₁×p₅ 0 1239 6×11×21 0 1239 1386 2625切割点 k2(A₁A₂)(A₃A₄A₅)OPT[1,2] OPT[3,5] p₀×p₂×p₅ 462 756 6×7×21 462 756 882 2100切割点 k3(A₁A₂A₃)(A₄A₅)OPT[1,3] OPT[4,5] p₀×p₃×p₅ 1092 945 6×15×21 1092 945 1890 3927切割点 k4(A₁A₂A₃A₄)(A₅)OPT[1,4] OPT[5,5] p₀×p₄×p₅ 744 0 6×3×21 744 0 378 1122✓最小OPT[1,5] min{2625, 2100, 3927, 1122} 1122K[1,5] 44. 结果与回溯最优连乘次数1122最优连乘顺序根据K表回溯得到((A(B(CD)))E)验证按此顺序计算C×D7×15×3 315B×(CD)11×7×3 231A×(B(CD))6×11×3 198(A(B(CD)))×E6×3×21 378总计315 231 198 378 1122 ✓5. 复杂度分析时间复杂度O(n³)三重循环空间复杂度O(n²)存储OPT表和K表关键洞察中间结果维度很重要尽量让中间结果维度小后续计算更省自底而上填表确保计算OPT(i, j)时所有子问题都已计算完成枚举所有切割点因为不知道哪个切割点最优必须全部枚举最优子结构全局最优解必须由局部最优解组成三、问题二钢条切割问题动态规划简化版问题描述给定一根长度为n英寸的钢条将其切割成整数长度的段每段可以单独出售。价格表如下长度英寸123456价格元144789目标设计动态规划算法使总收益最大化。问题特性最优子结构长度为n的钢条的最优切割方案包含子段的最优切割方案重叠子问题不同长度的切割方案会共享相同的子问题一维状态状态只依赖长度这一个维度比矩阵连乘更简单动态规划算法设计1. 状态定义r[i] 长度为 i 的钢条的最大收益2. 状态转移方程价格数组定义p[j]表示长度为 j 的钢条段的价格直接出售不切割根据价格表p[1] 1长度为1英寸的钢条价格1元p[2] 4长度为2英寸的钢条价格4元p[3] 4长度为3英寸的钢条价格4元p[4] 7长度为4英寸的钢条价格7元p[5] 8长度为5英寸的钢条价格8元p[6] 9长度为6英寸的钢条价格9元状态转移方程r[i] max{p[j] r[i-j] | 1 ≤ j ≤ i}逻辑解释对于长度为i的钢条枚举第一段的长度j1到i如果第一段长度为j收益为p[j]第一段长度为j直接出售的价格r[i-j]剩余部分长度为i-j的最优切割收益总收益 p[j] r[i-j]选择使总收益最大的j3. 填表过程n6初始化r[0] 0长度为0的钢条收益为0i1长度为1英寸的钢条j1第一段长度为1p[1] r[0] 1 0 1✓唯一选择r[1] 1切割方案不切割整根出售1英寸i2长度为2英寸的钢条j1第一段长度为1p[1] r[1] 1 1 2方案切成11收益 1 1 2j2第一段长度为2p[2] r[0] 4 0 4✓最大方案不切割整根出售2英寸收益 4r[2] max{2, 4} 4最优方案不切割整根出售i3长度为3英寸的钢条j1第一段长度为1p[1] r[2] 1 4 5✓最大方案切成12收益 1 4 5j2第一段长度为2p[2] r[1] 4 1 5✓同样最大方案切成21收益 4 1 5j3第一段长度为3p[3] r[0] 4 0 4方案不切割整根出售3英寸收益 4r[3] max{5, 5, 4} 5最优方案切成12或21i4长度为4英寸的钢条j1第一段长度为1p[1] r[3] 1 5 6方案切成13收益 1 5 6j2第一段长度为2p[2] r[2] 4 4 8✓最大方案切成22收益 4 4 8j3第一段长度为3p[3] r[1] 4 1 5方案切成31收益 4 1 5j4第一段长度为4p[4] r[0] 7 0 7方案不切割整根出售4英寸收益 7r[4] max{6, 8, 5, 7} 8最优方案切成22i5长度为5英寸的钢条j1第一段长度为1p[1] r[4] 1 8 9✓最大方案切成14收益 1 8 9j2第一段长度为2p[2] r[3] 4 5 9✓同样最大方案切成23收益 4 5 9j3第一段长度为3p[3] r[2] 4 4 8方案切成32收益 4 4 8j4第一段长度为4p[4] r[1] 7 1 8方案切成41收益 7 1 8j5第一段长度为5p[5] r[0] 8 0 8方案不切割整根出售5英寸收益 8r[5] max{9, 9, 8, 8, 8} 9最优方案切成14或23i6长度为6英寸的钢条j1第一段长度为1p[1] r[5] 1 9 10方案切成15收益 1 9 10j2第一段长度为2p[2] r[4] 4 8 12✓最大方案切成24进一步24可以优化为222收益 4 8 12j3第一段长度为3p[3] r[3] 4 5 9方案切成33收益 4 5 9j4第一段长度为4p[4] r[2] 7 4 11方案切成42收益 7 4 11j5第一段长度为5p[5] r[1] 8 1 9方案切成51收益 8 1 9j6第一段长度为6p[6] r[0] 9 0 9方案不切割整根出售6英寸收益 9r[6] max{10, 12, 9, 11, 9, 9} 12最优方案切成222三个2英寸段4. 结果最大收益r[6] 12元最优切割方案切成3段每段2英寸2 2 2 65. 复杂度分析时间复杂度O(n²)空间复杂度O(n)与矩阵连乘的对比特性矩阵连乘钢条切割状态维度二维 OPT(i,j)一维 r[i]状态转移枚举切割点k枚举第一段长度j复杂度O(n³)O(n²)难度较复杂较简单四、问题三苹果买卖问题贪心算法案例问题描述一辆卡车从城市A到城市B途经n个苹果市场。在每个市场i可以以价格B[i]买入苹果或以价格S[i]卖出苹果。目标在某个市场i买入在后续市场jj ≥ i卖出使利润 M S[j] - B[i] 最大化。约束卡车只能前进不能后退只能进行一次买入和一次卖出可以在同一市场买入和卖出为什么用贪心算法问题特性分析最优子结构如果(i, j)是最优买卖对那么i一定是1到j之间价格最低的市场贪心选择特性对于每个卖出位置j最优买入位置是j之前包括j价格最低的市场局部最优保证全局最优维护最低买入价格计算每个位置的最大利润与动态规划的区别不需要枚举所有可能的买卖对只需要一次遍历维护最低买入价格复杂度从O(n²)降为O(n)贪心算法设计1. 核心思路对于每个卖出位置j最优买入位置是j之前包括j价格最低的市场。2. 算法伪代码输入B[1..n]每个市场的买入价格数组S[1..n]每个市场的卖出价格数组n市场数量输出optimalBuyMarket最优买入市场编号sellMarket最优卖出市场编号maxProfit最大利润变量说明minBuy到当前位置为止的最低买入价格buyMarket当前最低买入价格对应的市场编号maxProfit到目前为止的最大利润sellMarket当前最大利润对应的卖出市场编号optimalBuyMarket当前最大利润对应的买入市场编号APPLE-TRADING(B, S, n) 1. minBuy ← B[1] // 初始化第一个市场的最低买入价格就是B[1] 2. buyMarket ← 1 // 初始化第一个市场作为当前最低买入价格的市场 3. maxProfit ← S[1] - B[1] // 初始化第一个市场的利润可能为负表示亏损 4. sellMarket ← 1 // 初始化第一个市场作为当前最优卖出市场 5. // 从第二个市场开始遍历 6. for j ← 2 to n // 遍历每个市场j作为潜在的卖出市场 7. do if B[j] minBuy // 如果市场j的买入价格低于当前最低买入价格 8. then minBuy ← B[j] // 更新最低买入价格为B[j] 9. buyMarket ← j // 更新最低买入价格对应的市场为j // 注意这里更新buyMarket但optimalBuyMarket可能不变 // 因为虽然找到了更低的买入价但可能利润不是最大的 10. // 计算在市场j卖出的利润 // 使用当前已知的最低买入价格可能在市场j之前 11. profit ← S[j] - minBuy // 利润 市场j的卖出价格 - 到j为止的最低买入价格 // 这保证了买入市场 ≤ 卖出市场j满足约束条件 12. if profit maxProfit // 如果当前利润大于已知的最大利润 13. then maxProfit ← profit // 更新最大利润 14. sellMarket ← j // 更新最优卖出市场为j 15. optimalBuyMarket ← buyMarket // 更新最优买入市场为当前buyMarket // 注意这里buyMarket是到j为止的最低买入价格对应的市场 // 这保证了(optimalBuyMarket, sellMarket)是最优买卖对 16. 17. return (optimalBuyMarket, sellMarket, maxProfit) // 返回最优买入市场、最优卖出市场和最大利润算法核心逻辑维护最低买入价格第7-9行在遍历过程中始终记录到当前位置为止的最低买入价格及其对应的市场。这是贪心选择的关键——对于每个卖出位置j最优买入位置一定是j之前包括j价格最低的市场。计算当前利润第11行对于每个市场j计算在最低买入价格的市场买入在市场j卖出的利润。这利用了贪心选择特性不需要枚举所有可能的买入位置。更新最优解第12-15行如果当前利润大于已知的最大利润更新最大利润和对应的买卖市场对。为什么这样设计是正确的对于任意卖出位置j如果我们已经知道j之前包括j的最低买入价格是minBuy对应的市场是buyMarket那么(buyMarket, j)就是在j卖出的最优买卖对。因为如果存在更优的买入位置kk j且B[k] minBuy那么算法应该已经在遍历到k时更新了minBuy和buyMarket。因此我们只需要遍历一次对每个卖出位置j用当前已知的最低买入价格计算利润即可。3. 算法执行示例假设输入B [5, 3, 2, 4, 1, 6] // 买入价格S [4, 6, 5, 7, 3, 8] // 卖出价格执行过程详解列说明j当前遍历到的市场编号作为潜在的卖出市场B[j]市场j的买入价格S[j]市场j的卖出价格minBuy到市场j为止的最低买入价格buyMarket当前最低买入价格对应的市场编号profit在市场j卖出的利润 S[j] - minBuymaxProfit到目前为止的最大利润sellMarket当前最大利润对应的卖出市场optimalBuyMarket当前最大利润对应的买入市场逐步执行过程j1初始化处理第一个市场B[1] 5S[1] 4minBuy 5第一个市场最低买入价格就是B[1]buyMarket 1最低买入价格对应的市场profit S[1] - minBuy 4 - 5 -1亏损1元maxProfit -1当前最大利润虽然是亏损sellMarket 1optimalBuyMarket 1含义如果只在市场1买卖会亏损1元j2处理第二个市场B[2] 3S[2] 6更新最低买入价格因为B[2] 3 minBuy 5所以minBuy 3更新为更低的价格buyMarket 2更新为市场2profit S[2] - minBuy 6 - 3 3利润3元更新最大利润因为profit 3 maxProfit -1所以maxProfit 3sellMarket 2最优卖出市场更新为市场2optimalBuyMarket 2最优买入市场更新为市场2含义在市场2买入价格3在市场2卖出价格6利润3元。这是目前最优方案。j3处理第三个市场B[3] 2S[3] 5更新最低买入价格因为B[3] 2 minBuy 3所以minBuy 2更新为更低的价格buyMarket 3更新为市场3profit S[3] - minBuy 5 - 2 3利润3元不更新最大利润因为profit 3 maxProfit 3没有更优sellMarket 2optimalBuyMarket 2保持不变含义虽然找到了更低的买入价格市场3价格2但在市场3卖出的利润3元没有超过当前最优利润3元所以最优方案仍然是市场2市场2。j4处理第四个市场B[4] 4S[4] 7不更新最低买入价格因为B[4] 4 minBuy 2所以minBuy和buyMarket保持不变profit S[4] - minBuy 7 - 2 5利润5元注意这里使用的是市场3的买入价格minBuy2而不是市场4的买入价格更新最大利润因为profit 5 maxProfit 3所以maxProfit 5sellMarket 4最优卖出市场更新为市场4optimalBuyMarket 3最优买入市场更新为市场3即当前的buyMarket含义在市场3买入价格2在市场4卖出价格7利润5元。这是新的最优方案。j5处理第五个市场B[5] 1S[5] 3更新最低买入价格因为B[5] 1 minBuy 2所以minBuy 1更新为更低的价格buyMarket 5更新为市场5profit S[5] - minBuy 3 - 1 2利润2元不更新最大利润因为profit 2 maxProfit 5所以最优方案保持不变sellMarket 4optimalBuyMarket 3保持不变含义虽然找到了更低的买入价格市场5价格1但在市场5卖出的利润2元没有超过当前最优利润5元所以最优方案仍然是市场3市场4。j6处理第六个市场最终结果B[6] 6S[6] 8不更新最低买入价格因为B[6] 6 minBuy 1所以minBuy和buyMarket保持不变profit S[6] - minBuy 8 - 1 7利润7元注意这里使用的是市场5的买入价格minBuy1而不是市场6的买入价格更新最大利润因为profit 7 maxProfit 5所以maxProfit 7sellMarket 6最优卖出市场更新为市场6optimalBuyMarket 5最优买入市场更新为市场5即当前的buyMarket含义在市场5买入价格1在市场6卖出价格8利润7元。这是最终的最优方案。最终结果最优买入市场5价格1元/斤最优卖出市场6价格8元/斤最大利润7元/斤关键洞察minBuy和buyMarket的更新每当遇到更低的买入价格时更新这保证了对于每个卖出位置j我们总是使用j之前包括j的最低买入价格。profit的计算总是使用当前的minBuy计算而不是B[j]这体现了贪心选择特性。最优解的更新只有当profit大于maxProfit时才更新这保证了我们找到的是全局最优解。4. 正确性证明贪心选择特性对于任意卖出位置j最优买入位置一定是j之前包括j价格最低的市场。证明反证法假设存在更优的买入位置kk i且B[k] B[i]其中i是j之前价格最低的市场那么(k, j)的利润 S[j] - B[k] S[j] - B[i] (i, j)的利润但这与i是j之前价格最低的市场矛盾因为如果B[k] B[i]算法应该已经将minBuy更新为B[k]5. 复杂度分析时间复杂度O(n)单次遍历空间复杂度O(1)只使用常数个变量与动态规划的对比如果用动态规划状态定义F[i][j] 在市场i买入、市场j卖出的利润需要计算所有O(n²)个状态复杂度O(n²)贪心算法的优势只需要O(n)时间代码更简单空间复杂度O(1)五、三种问题的算法选择决策树问题是否满足最优子结构 ├─ 否 → 不适合用DP或贪心考虑其他算法 └─ 是 → 是否满足贪心选择特性 ├─ 是 → 优先用贪心算法 │ ├─ 苹果买卖O(n)时间O(1)空间 │ └─ 区间调度无权重O(n log n)时间 └─ 否 → 用动态规划 ├─ 矩阵连乘O(n³)时间O(n²)空间 └─ 钢条切割O(n²)时间O(n)空间问题特征对比表问题算法类型状态维度时间复杂度空间复杂度关键特性矩阵连乘动态规划二维O(n³)O(n²)重叠子问题、最优子结构钢条切割动态规划一维O(n²)O(n)重叠子问题、最优子结构苹果买卖贪心算法无状态表O(n)O(1)贪心选择特性、最优子结构六、总结算法选择的决策框架核心原则先判断最优子结构如果不满足不适合用DP或贪心再判断贪心选择特性如果满足优先用贪心通常更简单高效最后选择动态规划如果只满足最优子结构用DP性能对比算法类型时间复杂度空间复杂度实现难度适用场景贪心算法O(n) 或 O(n log n)O(1) 或 O(n)简单满足贪心选择特性动态规划O(n²) 或 O(n³)O(n) 或 O(n²)中等满足最优子结构