企业网站建设浩森宇特广州建企业网站
张小明 2025/12/30 3:09:53
企业网站建设浩森宇特,广州建企业网站,乐清人才网官方网站,广州网站排名推广文章目录习题一#xff1a;矩阵链乘法问题——动态规划#x1f4d6; 问题描述#xff1a;找到最优的矩阵乘法顺序正确思路#xff1a;动态规划1️⃣ 问题分解的逻辑2️⃣ 递推关系#xff1a;自底向上计算3️⃣ 计算过程#xff1a;第n层使用n-1层的结果4️⃣ 两个表格矩阵链乘法问题——动态规划 问题描述找到最优的矩阵乘法顺序正确思路动态规划1️⃣ 问题分解的逻辑2️⃣ 递推关系自底向上计算3️⃣ 计算过程第n层使用n-1层的结果4️⃣ 两个表格记录最优值和最优解表格1m [ i , j ] m[i,j]m[i,j]- 记录最小乘法次数表格2s [ i , j ] s[i,j]s[i,j]- 记录最优分割位置 算法执行过程示例步骤1初始化长度 l 1步骤2计算长度为2的链l 2步骤3计算长度为3的链l 3步骤4计算长度为4的链l 4步骤5计算长度为5的链l 5最终表格回溯构造最优解第1步处理整个链[ 1 , 5 ] [1,5][1,5]第2步递归处理左部分[ 1 , 4 ] [1,4][1,4]第3步递归处理[ 2 , 4 ] [2,4][2,4]第4步简化括号⚠️ 常见错误与注意事项错误维度数组索引错误 算法复杂度分析时间复杂度 拓展思考习题2钢条切割问题——动态规划 问题描述最大化钢条切割收益正确思路动态规划1️⃣ 问题分解的逻辑2️⃣ 递推关系自底向上计算3️⃣ 计算过程第k层使用1到k-1层的结果4️⃣ 两个表格记录最优值和最优切割策略表格1R [ k ] R[k]R[k]- 记录最大收益表格2C [ k ] C[k]C[k]- 记录最优切割点 算法伪代码 算法执行过程示例步骤1初始化长度 k 1步骤2计算长度 k 2步骤3计算长度 k 3步骤4计算长度 k 4步骤5计算长度 k 5步骤6计算长度 k 6最终表格回溯构造最优切割方案对于长度为6的钢条递归处理左段长度为2递归处理右段长度为4递归处理两个长度为2的段回溯算法伪代码⚠️ 常见错误与注意事项错误1忘记考虑不切割的情况错误2没有利用对称性优化 算法复杂度分析时间复杂度 拓展思考习题一矩阵链乘法问题——动态规划⏱️预计阅读时间20-25分钟学习目标掌握如何用动态规划解决矩阵链乘法问题理解动态规划的两步计算最优值和记录最优解 问题描述找到最优的矩阵乘法顺序注意矩阵连乘分为两部分首先是根据递推公式计算最小乘法次数然后需要记录最优分割位置。求解过程需要体现以上两部分正确思路动态规划动态规划的核心思想将大问题分解为重叠子问题自底向上求解避免重复计算。1️⃣ 问题分解的逻辑核心观察计算矩阵链A i × A i 1 × ⋯ × A j A_i \times A_{i1} \times \cdots \times A_jAi×Ai1×⋯×Aj的最优方式必然在某个位置k kk进行分割。分解思路选择一个分割点k kki ≤ k j i \leq k ji≤kj将矩阵链分成两部分左子链A i × A i 1 × ⋯ × A k A_i \times A_{i1} \times \cdots \times A_kAi×Ai1×⋯×Ak右子链A k 1 × A k 2 × ⋯ × A j A_{k1} \times A_{k2} \times \cdots \times A_jAk1×Ak2×⋯×Aj最优子结构性质如果整个链的计算方式是最优的那么左子链和右子链的计算方式也必然是最优的否则可以用更优的子链计算方式替换得到更优的整体方案矛盾总成本分解总成本 左子链成本 右子链成本 合并成本 \text{总成本} \text{左子链成本} \text{右子链成本} \text{合并成本}总成本左子链成本右子链成本合并成本其中左子链成本计算A i × ⋯ × A k A_i \times \cdots \times A_kAi×⋯×Ak的最少乘法次数右子链成本计算A k 1 × ⋯ × A j A_{k1} \times \cdots \times A_jAk1×⋯×Aj的最少乘法次数合并成本将两个结果矩阵相乘的代价 p i − 1 × p k × p j p_{i-1} \times p_k \times p_jpi−1×pk×pj左子链结果维度p [ i − 1 ] × p [ k ] p[i-1] \times p[k]p[i−1]×p[k]右子链结果维度p [ k ] × p [ j ] p[k] \times p[j]p[k]×p[j]合并乘法次数p [ i − 1 ] × p [ k ] × p [ j ] p[i-1] \times p[k] \times p[j]p[i−1]×p[k]×p[j]尝试所有分割点由于不知道哪个k kk是最优的需要尝试所有可能的分割点选择总成本最小的那个p pp数组说明p pp是维度数组矩阵A i A_iAi的维度是p [ i − 1 ] × p [ i ] p[i-1] \times p[i]p[i−1]×p[i]。例如p [ 6 , 11 , 7 , 15 , 3 , 21 ] p [6, 11, 7, 15, 3, 21]p[6,11,7,15,3,21]表示A 1 A_1A1是6 × 11 6 \times 116×11A 2 A_2A2是11 × 7 11 \times 711×7等等。2️⃣ 递推关系自底向上计算状态定义m [ i , j ] m[i,j]m[i,j]计算A i × A i 1 × ⋯ × A j A_i \times A_{i1} \times \cdots \times A_jAi×Ai1×⋯×Aj所需的最少标量乘法次数递推公式m [ i , j ] { 0 , if i j 单个矩阵无需乘法 min i ≤ k j { m [ i , k ] m [ k 1 , j ] p i − 1 × p k × p j } , if i j m[i,j] \begin{cases} 0, \text{if } i j \quad \text{单个矩阵无需乘法} \\ \min_{i \leq k j} \{m[i,k] m[k1,j] p_{i-1} \times p_k \times p_j\}, \text{if } i j \end{cases}m[i,j]{0,mini≤kj{m[i,k]m[k1,j]pi−1×pk×pj},ifij单个矩阵无需乘法ifij关键理解基础情况i j i jij时只有一个矩阵成本为0 00递归情况i j i jij时尝试所有分割点k kk选择成本最小的3️⃣ 计算过程第n层使用n-1层的结果动态规划的自底向上特性按链的长度递增计算确保计算m [ i , j ] m[i,j]m[i,j]时所有更短的子链已经计算完成。计算顺序第1层长度 l 1单个矩阵m [ 1 , 1 ] , m [ 2 , 2 ] , … , m [ n , n ] 0 m[1,1], m[2,2], \ldots, m[n,n] 0m[1,1],m[2,2],…,m[n,n]0基础情况直接得到第2层长度 l 2两个矩阵相乘计算m [ 1 , 2 ] , m [ 2 , 3 ] , … , m [ n − 1 , n ] m[1,2], m[2,3], \ldots, m[n-1,n]m[1,2],m[2,3],…,m[n−1,n]使用第1层的结果m [ i , i ] m[i,i]m[i,i]和m [ j , j ] m[j,j]m[j,j]第3层长度 l 3三个矩阵相乘计算m [ 1 , 3 ] , m [ 2 , 4 ] , … , m [ n − 2 , n ] m[1,3], m[2,4], \ldots, m[n-2,n]m[1,3],m[2,4],…,m[n−2,n]使用第1层和第2层的结果m [ i , k ] m[i,k]m[i,k]和m [ k 1 , j ] m[k1,j]m[k1,j]长度 ≤ 2…第n层长度 l n所有矩阵相乘计算m [ 1 , n ] m[1,n]m[1,n]使用所有前面层的结果关键点计算长度为l ll的链时需要用到长度 l ll的链的结果这保证了子问题已经求解可以直接查表使用避免了重复计算每个子问题只计算一次4️⃣ 两个表格记录最优值和最优解矩阵链乘法问题需要两个表格来完整解决问题表格1m [ i , j ] m[i,j]m[i,j]- 记录最小乘法次数作用存储子问题的最优值m [ i , j ] m[i,j]m[i,j] 计算A i × ⋯ × A j A_i \times \cdots \times A_jAi×⋯×Aj的最少乘法次数为什么需要避免重复计算相同的子问题在计算m [ i , j ] m[i,j]m[i,j]时可以直接查表获取m [ i , k ] m[i,k]m[i,k]和m [ k 1 , j ] m[k1,j]m[k1,j]的值表格2s [ i , j ] s[i,j]s[i,j]- 记录最优分割位置作用存储子问题的最优解用于回溯。s [ i , j ] s[i,j]s[i,j] 在计算A i × ⋯ × A j A_i \times \cdots \times A_jAi×⋯×Aj时的最优分割点k kk两个表格的关系在计算m [ i , j ] m[i,j]m[i,j]时同时更新s [ i , j ] s[i,j]s[i,j]当找到使m [ i , j ] m[i,j]m[i,j]最小的k kk时记录s [ i , j ] k s[i,j] ks[i,j]k回溯时根据s [ i , j ] s[i,j]s[i,j]递归地构造最优括号化方案回溯过程如果 s[i,j] k则最优括号化是 (A_i × ... × A_k) × (A_{k1} × ... × A_j) 递归地 - 左部分根据 s[i,k] 继续分解 - 右部分根据 s[k1,j] 继续分解 算法执行过程示例让我们用示例数据演示算法执行过程数据5个矩阵维度数组p [ 6 , 11 , 7 , 15 , 3 , 21 ] p [6, 11, 7, 15, 3, 21]p[6,11,7,15,3,21]步骤1初始化长度 l 1单个矩阵的成本为 0m [ i , j ] m[i,j]m[i,j]j1j2j3j4j5i10 (6×11)i20 (11×7)i30 (7×15)i40 (15×3)i50 (3×21)步骤2计算长度为2的链l 2计算m [ 1 , 2 ] m[1,2]m[1,2]矩阵 A×Bk 1 k1k1m [ 1 , 1 ] m [ 2 , 2 ] p 0 × p 1 × p 2 0 0 6 × 11 × 7 462 m[1,1] m[2,2] p_0 \times p_1 \times p_2 0 0 6 \times 11 \times 7 462m[1,1]m[2,2]p0×p1×p2006×11×7462m [ 1 , 2 ] 462 m[1,2] 462m[1,2]462s [ 1 , 2 ] 1 s[1,2] 1s[1,2]1计算m [ 2 , 3 ] m[2,3]m[2,3]矩阵 B×Ck 2 k2k20 0 11 × 7 × 15 1155 0 0 11 \times 7 \times 15 11550011×7×151155m [ 2 , 3 ] 1155 m[2,3] 1155m[2,3]1155s [ 2 , 3 ] 2 s[2,3] 2s[2,3]2计算m [ 3 , 4 ] m[3,4]m[3,4]矩阵 C×Dk 3 k3k30 0 7 × 15 × 3 315 0 0 7 \times 15 \times 3 315007×15×3315m [ 3 , 4 ] 315 m[3,4] 315m[3,4]315s [ 3 , 4 ] 3 s[3,4] 3s[3,4]3计算m [ 4 , 5 ] m[4,5]m[4,5]矩阵 D×Ek 4 k4k40 0 15 × 3 × 21 945 0 0 15 \times 3 \times 21 9450015×3×21945m [ 4 , 5 ] 945 m[4,5] 945m[4,5]945s [ 4 , 5 ] 4 s[4,5] 4s[4,5]4步骤3计算长度为3的链l 3计算m [ 1 , 3 ] m[1,3]m[1,3]矩阵 A×B×Ck 1 k1k1m [ 1 , 1 ] m [ 2 , 3 ] p 0 × p 1 × p 3 0 1155 6 × 11 × 15 0 1155 990 2145 m[1,1] m[2,3] p_0 \times p_1 \times p_3 0 1155 6 \times 11 \times 15 0 1155 990 2145m[1,1]m[2,3]p0×p1×p3011556×11×15011559902145k 2 k2k2m [ 1 , 2 ] m [ 3 , 3 ] p 0 × p 2 × p 3 462 0 6 × 7 × 15 462 0 630 1092 m[1,2] m[3,3] p_0 \times p_2 \times p_3 462 0 6 \times 7 \times 15 462 0 630 1092m[1,2]m[3,3]p0×p2×p346206×7×1546206301092最小值m [ 1 , 3 ] 1092 m[1,3] 1092m[1,3]1092s [ 1 , 3 ] 2 s[1,3] 2s[1,3]2计算m [ 2 , 4 ] m[2,4]m[2,4]矩阵 B×C×Dk 2 k2k20 315 11 × 7 × 3 546 0 315 11 \times 7 \times 3 546031511×7×3546k 3 k3k31155 0 11 × 15 × 3 1155 495 1650 1155 0 11 \times 15 \times 3 1155 495 16501155011×15×311554951650最小值m [ 2 , 4 ] 546 m[2,4] 546m[2,4]546s [ 2 , 4 ] 2 s[2,4] 2s[2,4]2计算m [ 3 , 5 ] m[3,5]m[3,5]矩阵 C×D×Ek 3 k3k30 945 7 × 15 × 21 0 945 2205 3150 0 945 7 \times 15 \times 21 0 945 2205 315009457×15×21094522053150k 4 k4k4315 0 7 × 3 × 21 315 0 441 756 315 0 7 \times 3 \times 21 315 0 441 75631507×3×213150441756最小值m [ 3 , 5 ] 756 m[3,5] 756m[3,5]756s [ 3 , 5 ] 4 s[3,5] 4s[3,5]4步骤4计算长度为4的链l 4计算m [ 1 , 4 ] m[1,4]m[1,4]矩阵 A×B×C×Dk 1 k1k10 546 6 × 11 × 3 0 546 198 744 0 546 6 \times 11 \times 3 0 546 198 74405466×11×30546198744k 2 k2k2462 315 6 × 7 × 3 462 315 126 903 462 315 6 \times 7 \times 3 462 315 126 9034623156×7×3462315126903k 3 k3k31092 0 6 × 15 × 3 1092 0 270 1362 1092 0 6 \times 15 \times 3 1092 0 270 1362109206×15×3109202701362最小值m [ 1 , 4 ] 744 m[1,4] 744m[1,4]744s [ 1 , 4 ] 1 s[1,4] 1s[1,4]1计算m [ 2 , 5 ] m[2,5]m[2,5]矩阵 B×C×D×Ek 2 k2k20 756 11 × 7 × 21 0 756 1617 2373 0 756 11 \times 7 \times 21 0 756 1617 2373075611×7×21075616172373k 3 k3k31155 945 11 × 15 × 21 1155 945 3465 5565 1155 945 11 \times 15 \times 21 1155 945 3465 5565115594511×15×21115594534655565k 4 k4k4546 0 11 × 3 × 21 546 0 693 1239 546 0 11 \times 3 \times 21 546 0 693 1239546011×3×2154606931239最小值m [ 2 , 5 ] 1239 m[2,5] 1239m[2,5]1239s [ 2 , 5 ] 4 s[2,5] 4s[2,5]4步骤5计算长度为5的链l 5计算m [ 1 , 5 ] m[1,5]m[1,5]矩阵 A×B×C×D×Ek 1 k1k10 1239 6 × 11 × 21 0 1239 1386 2625 0 1239 6 \times 11 \times 21 0 1239 1386 2625012396×11×210123913862625k 2 k2k2462 756 6 × 7 × 21 462 756 882 2100 462 756 6 \times 7 \times 21 462 756 882 21004627566×7×214627568822100k 3 k3k31092 945 6 × 15 × 21 1092 945 1890 3927 1092 945 6 \times 15 \times 21 1092 945 1890 392710929456×15×21109294518903927k 4 k4k4744 0 6 × 3 × 21 744 0 378 1122 744 0 6 \times 3 \times 21 744 0 378 112274406×3×2174403781122最小值m [ 1 , 5 ] 1122 m[1,5] 1122m[1,5]1122s [ 1 , 5 ] 4 s[1,5] 4s[1,5]4最终表格m [ i , j ] m[i,j]m[i,j]表格最小乘法次数m [ i , j ] m[i,j]m[i,j]j1j2j3j4j5i1046210927441122i2011555461239i30315756i40945i50s [ i , j ] s[i,j]s[i,j]表格最优分割位置s [ i , j ] s[i,j]s[i,j]j1j2j3j4j5i1-1214i2-224i3-34i4-4i5-回溯构造最优解回溯的核心逻辑s [ i , j ] k s[i,j] ks[i,j]k表示计算A i × ⋯ × A j A_i \times \cdots \times A_jAi×⋯×Aj时最优分割点在位置k kk。这意味着先计算A i × ⋯ × A k A_i \times \cdots \times A_kAi×⋯×Ak再计算A k 1 × ⋯ × A j A_{k1} \times \cdots \times A_jAk1×⋯×Aj最后合并用括号表示( A i × ⋯ × A k ) × ( A k 1 × ⋯ × A j ) (A_i \times \cdots \times A_k) \times (A_{k1} \times \cdots \times A_j)(Ai×⋯×Ak)×(Ak1×⋯×Aj)然后递归地对左右两部分进行括号化回溯过程递归展开第1步处理整个链[ 1 , 5 ] [1,5][1,5]查表s [ 1 , 5 ] 4 s[1,5] 4s[1,5]4含义在位置4分割得到( A 1 × A 2 × A 3 × A 4 ) × ( A 5 ) (A_1 \times A_2 \times A_3 \times A_4) \times (A_5)(A1×A2×A3×A4)×(A5)当前状态( A 1 A 2 A 3 A 4 ) × A 5 (A_1 A_2 A_3 A_4) \times A_5(A1A2A3A4)×A5第2步递归处理左部分[ 1 , 4 ] [1,4][1,4]查表s [ 1 , 4 ] 1 s[1,4] 1s[1,4]1含义在位置1分割A 1 × A 2 × A 3 × A 4 A_1 \times A_2 \times A_3 \times A_4A1×A2×A3×A4得到( A 1 ) × ( A 2 × A 3 × A 4 ) (A_1) \times (A_2 \times A_3 \times A_4)(A1)×(A2×A3×A4)更新状态( ( A 1 ) × ( A 2 A 3 A 4 ) ) × A 5 ((A_1) \times (A_2 A_3 A_4)) \times A_5((A1)×(A2A3A4))×A5第3步递归处理[ 2 , 4 ] [2,4][2,4]查表s [ 2 , 4 ] 2 s[2,4] 2s[2,4]2含义在位置2分割A 2 × A 3 × A 4 A_2 \times A_3 \times A_4A2×A3×A4得到( A 2 ) × ( A 3 × A 4 ) (A_2) \times (A_3 \times A_4)(A2)×(A3×A4)更新状态( ( A 1 ) × ( ( A 2 ) × ( A 3 A 4 ) ) ) × A 5 ((A_1) \times ((A_2) \times (A_3 A_4))) \times A_5((A1)×((A2)×(A3A4)))×A5第4步简化括号由于单个矩阵不需要括号简化后得到最优括号化方案( ( A ( B ( C D ) ) ) E ) ((A(B(CD)))E)((A(B(CD)))E)其中A A 1 A A_1AA1B A 2 B A_2BA2C A 3 C A_3CA3D A 4 D A_4DA4E A 5 E A_5EA5⚠️ 常见错误与注意事项错误维度数组索引错误常见错误混淆矩阵编号从1开始和数组索引从0开始计算合并成本时用错维度正确理解矩阵A i A_iAi的维度是p [ i − 1 ] × p [ i ] p[i-1] \times p[i]p[i−1]×p[i]计算A i × ⋯ × A k A_i \times \cdots \times A_kAi×⋯×Ak和A k 1 × ⋯ × A j A_{k1} \times \cdots \times A_jAk1×⋯×Aj的合并成本左结果矩阵维度p [ i − 1 ] × p [ k ] p[i-1] \times p[k]p[i−1]×p[k]右结果矩阵维度p [ k ] × p [ j ] p[k] \times p[j]p[k]×p[j]合并成本p [ i − 1 ] × p [ k ] × p [ j ] p[i-1] \times p[k] \times p[j]p[i−1]×p[k]×p[j] 算法复杂度分析时间复杂度递推关系T ( n ) O ( n 3 ) T(n) O(n^3)T(n)O(n3)分析外层循环链的长度l ll从 2 到n nn共n − 1 n-1n−1次中层循环起始位置i ii从 1 到n − l 1 n-l1n−l1平均约n / 2 n/2n/2次内层循环分割点k kk从i ii到j − 1 j-1j−1平均约l / 2 l/2l/2次总时间复杂度O ( n 3 ) O(n^3)O(n3) 拓展思考为什么不能用贪心法局部最优不等于全局最优需要尝试所有可能的分割点。为什么时间复杂度是O ( n 3 ) O(n^3)O(n3)三层嵌套循环长度、起始位置、分割点。如何优化可以使用记忆化递归但时间复杂度仍然是O ( n 3 ) O(n^3)O(n3)。实际应用编译器优化、数值计算、图像处理等领域都有应用。记忆口诀矩阵链乘用DP两个表格要记牢m表记录最优值s表回溯找方案习题2钢条切割问题——动态规划适合对象学习动态规划算法的同学⏱️预计阅读时间20-25分钟学习目标掌握如何用动态规划解决钢条切割问题理解动态规划的两步计算最优值和记录最优切割策略 问题描述最大化钢条切割收益目标设计动态规划算法确定如何切割钢条以最大化总收益提供算法伪代码分析算法的时间复杂度和空间复杂度正确思路动态规划动态规划的核心思想将大问题分解为重叠子问题自底向上求解避免重复计算。1️⃣ 问题分解的逻辑分解思路选择第一次切割位置如果不切割直接卖出收益为p k p_kpk如果切割在位置i ii1 ≤ i ≤ k − 1 1 \leq i \leq k-11≤i≤k−1切割得到左段长度为i ii收益为R [ i ] R[i]R[i]最优切割方案下的收益右段长度为k − i k-ik−i收益为R [ k − i ] R[k-i]R[k−i]最优切割方案下的收益总收益R [ i ] R [ k − i ] R[i] R[k-i]R[i]R[k−i]最优子结构性质如果长度为k kk的钢条的最优切割方案是切割成i ii和k − i k-ik−i两段那么长度为i ii和k − i k-ik−i的钢条也必然采用最优切割方案否则可以用更优的子方案替换得到更优的整体方案矛盾尝试所有可能尝试所有可能的第一次切割位置i ii1 ≤ i ≤ k − 1 1 \leq i \leq k-11≤i≤k−1比较不切割的收益p k p_kpk和所有切割方案的收益R [ i ] R [ k − i ] R[i] R[k-i]R[i]R[k−i]选择收益最大的方案2️⃣ 递推关系自底向上计算状态定义R [ k ] R[k]R[k]切割长度为k kk英寸的钢条能够带来的最大收益基础情况R [ 1 ] p 1 R[1] p_1R[1]p1长度为1的钢条无法再切割只能直接卖出递推公式R [ k ] max { max 1 ≤ i ≤ k − 1 { R [ i ] R [ k − i ] } , p k } R[k] \max \left\{ \max_{1 \leq i \leq k-1} \{R[i] R[k-i]\}, \quad p_k \right\}R[k]max{1≤i≤k−1max{R[i]R[k−i]},pk}解释不切割收益为p k p_kpk切割尝试所有切割位置i ii选择R [ i ] R [ k − i ] R[i] R[k-i]R[i]R[k−i]的最大值最终取两者的最大值优化版本利用对称性由于切割成i ii和k − i k-ik−i与切割成k − i k-ik−i和i ii是等价的可以只考虑i ≤ k / 2 i \leq k/2i≤k/2R [ k ] max { max 1 ≤ i ≤ ⌊ k / 2 ⌋ { R [ i ] R [ k − i ] } , p k } R[k] \max \left\{ \max_{1 \leq i \leq \lfloor k/2 \rfloor} \{R[i] R[k-i]\}, \quad p_k \right\}R[k]max{1≤i≤⌊k/2⌋max{R[i]R[k−i]},pk}这样可以减少一半的计算量。3️⃣ 计算过程第k层使用1到k-1层的结果动态规划的自底向上特性按长度递增计算确保计算R [ k ] R[k]R[k]时所有更短的钢条的最优收益已经计算完成。计算顺序第1层长度 k 1R [ 1 ] p 1 R[1] p_1R[1]p1基础情况直接得到第2层长度 k 2计算R [ 2 ] R[2]R[2]使用第1层的结果R [ 1 ] R[1]R[1]R [ 2 ] max { R [ 1 ] R [ 1 ] , p 2 } R[2] \max\{R[1] R[1], p_2\}R[2]max{R[1]R[1],p2}第3层长度 k 3计算R [ 3 ] R[3]R[3]使用第1层和第2层的结果R [ 1 ] R[1]R[1]和R [ 2 ] R[2]R[2]R [ 3 ] max { R [ 1 ] R [ 2 ] , R [ 2 ] R [ 1 ] , p 3 } max { R [ 1 ] R [ 2 ] , p 3 } R[3] \max\{R[1] R[2], R[2] R[1], p_3\} \max\{R[1] R[2], p_3\}R[3]max{R[1]R[2],R[2]R[1],p3}max{R[1]R[2],p3}利用对称性…第n层长度 k n计算R [ n ] R[n]R[n]使用所有前面层的结果R [ 1 ] , R [ 2 ] , … , R [ n − 1 ] R[1], R[2], \ldots, R[n-1]R[1],R[2],…,R[n−1]关键点计算长度为k kk的钢条时需要用到长度 k kk的钢条的最优收益这保证了子问题已经求解可以直接查表使用避免了重复计算每个子问题只计算一次4️⃣ 两个表格记录最优值和最优切割策略钢条切割问题需要两个表格来完整解决问题表格1R [ k ] R[k]R[k]- 记录最大收益作用存储子问题的最优值R [ k ] R[k]R[k] 切割长度为k kk的钢条能够带来的最大收益为什么需要避免重复计算相同的子问题在计算R [ k ] R[k]R[k]时可以直接查表获取R [ i ] R[i]R[i]和R [ k − i ] R[k-i]R[k−i]的值表格2C [ k ] C[k]C[k]- 记录最优切割点作用存储子问题的最优解用于回溯C [ k ] C[k]C[k] 切割长度为k kk的钢条时的最优第一次切割位置如果C [ k ] nil C[k] \text{nil}C[k]nil表示不切割直接卖出整根钢条为什么需要R [ k ] R[k]R[k]只告诉我们最优值是多少最大收益是多少C [ k ] C[k]C[k]告诉我们最优解是什么如何切割才能达到这个最大收益没有C [ k ] C[k]C[k]无法构造出最优的切割方案两个表格的关系在计算R [ k ] R[k]R[k]时同时更新C [ k ] C[k]C[k]当找到使R [ k ] R[k]R[k]最大的切割位置i ii时记录C [ k ] i C[k] iC[k]i如果p k p_kpk更大记录C [ k ] nil C[k] \text{nil}C[k]nil不切割回溯时根据C [ k ] C[k]C[k]递归地构造最优切割方案回溯过程如果 C[k] nil则长度为k的钢条不切割直接卖出 如果 C[k] i则最优切割是 长度为i的钢条根据C[i]继续切割 长度为k-i的钢条根据C[k-i]继续切割 算法伪代码算法Rod-Cutting(P[], n) 输入价格数组P[1..n]钢条长度n 输出最大收益R[n]最优切割策略 1. // 初始化长度为1的钢条 2. R[1] ← P[1] 3. C[1] ← nil // 长度为1无法切割 4. 4. // 自底向上计算 5. for k ← 2 to n do // k是钢条长度长度为1的情况已在第2行解决 6. // 情况1不切割直接卖出 7. q ← P[k] // 第3、4行指长度为k的钢条作为一个整体不切割的情况 8. C[k] ← nil 10. 9. // 情况2尝试所有切割位置 10. for i ← 1 to ⌊k/2⌋ do // 变换切割点利用对称性只需考虑i≤k/2 11. // 如果切割成i和k-i两段更优 12. if q R[i] R[k-i] then 13. q ← R[i] R[k-i] 14. C[k] ← i // 记录最优切割点 15. end if 16. end for 19. 17. R[k] ← q // 记录最大收益 18. end for 22. 19. return R[n] 算法执行过程示例让我们用示例数据演示算法执行过程数据n 6 n 6n6价格表P [ 1 , 4 , 4 , 7 , 8 , 9 ] P [1, 4, 4, 7, 8, 9]P[1,4,4,7,8,9]步骤1初始化长度 k 1R [ 1 ] P [ 1 ] 1 R[1] P[1] 1R[1]P[1]1C [ 1 ] nil C[1] \text{nil}C[1]nil长度为1无法切割步骤2计算长度 k 2不切割P [ 2 ] 4 P[2] 4P[2]4切割i 1 i1i1R [ 1 ] R [ 1 ] 1 1 2 R[1] R[1] 1 1 2R[1]R[1]112最大值max { 2 , 4 } 4 \max\{2, 4\} 4max{2,4}4R [ 2 ] 4 R[2] 4R[2]4C [ 2 ] nil C[2] \text{nil}C[2]nil不切割更优步骤3计算长度 k 3不切割P [ 3 ] 4 P[3] 4P[3]4切割i 1 i1i1R [ 1 ] R [ 2 ] 1 4 5 R[1] R[2] 1 4 5R[1]R[2]145i 2 i2i2这里对称结果一样最大值max { 5 , 4 } 5 \max\{5, 4\} 5max{5,4}5R [ 3 ] 5 R[3] 5R[3]5C [ 3 ] 1 C[3] 1C[3]1在位置1切割步骤4计算长度 k 4不切割P [ 4 ] 7 P[4] 7P[4]7切割i 1 i1i1R [ 1 ] R [ 3 ] 1 5 6 R[1] R[3] 1 5 6R[1]R[3]156i 2 i2i2R [ 2 ] R [ 2 ] 4 4 8 R[2] R[2] 4 4 8R[2]R[2]448最大值max { 6 , 8 , 7 } 8 \max\{6, 8, 7\} 8max{6,8,7}8R [ 4 ] 8 R[4] 8R[4]8C [ 4 ] 2 C[4] 2C[4]2在位置2切割步骤5计算长度 k 5不切割P [ 5 ] 8 P[5] 8P[5]8切割i是全局位置i 1 i1i1R [ 1 ] R [ 4 ] 1 8 9 R[1] R[4] 1 8 9R[1]R[4]189i 2 i2i2R [ 2 ] R [ 3 ] 4 5 9 R[2] R[3] 4 5 9R[2]R[3]459最大值max { 9 , 9 , 8 } 9 \max\{9, 9, 8\} 9max{9,9,8}9R [ 5 ] 9 R[5] 9R[5]9C [ 5 ] 1 C[5] 1C[5]1在位置1切割i 1 i1i1和i 2 i2i2收益相同选择较小的i ii步骤6计算长度 k 6不切割P [ 6 ] 9 P[6] 9P[6]9切割i 1 i1i1R [ 1 ] R [ 5 ] 1 9 10 R[1] R[5] 1 9 10R[1]R[5]1910i 2 i2i2R [ 2 ] R [ 4 ] 4 8 12 R[2] R[4] 4 8 12R[2]R[4]4812i 3 i3i3R [ 3 ] R [ 3 ] 5 5 10 R[3] R[3] 5 5 10R[3]R[3]5510最大值max { 10 , 12 , 10 , 9 } 12 \max\{10, 12, 10, 9\} 12max{10,12,10,9}12R [ 6 ] 12 R[6] 12R[6]12C [ 6 ] 2 C[6] 2C[6]2在位置2切割最终表格R [ i ] R[i]R[i]表格最大收益i ii123456R [ i ] R[i]R[i]元1458912C [ i ] C[i]C[i]表格最优切割点i ii123456C [ i ] C[i]C[i]英寸nilnil1212注意i是全局位置。回溯构造最优切割方案回溯的核心逻辑C [ k ] nil C[k] \text{nil}C[k]nil表示长度为k kk的钢条不切割直接卖出C [ k ] i C[k] iC[k]i表示长度为k kk的钢条在位置i ii切割得到长度为i ii和k − i k-ik−i的两段然后递归地对左右两段进行切割回溯过程递归展开对于长度为6的钢条查表C [ 6 ] 2 C[6] 2C[6]2含义在位置2切割得到左段长度为2右段长度为4递归处理左段长度为2查表C [ 2 ] nil C[2] \text{nil}C[2]nil含义长度为2的钢条不切割直接卖出递归处理右段长度为4查表C [ 4 ] 2 C[4] 2C[4]2含义在位置2切割得到左段长度为2右段长度为2递归处理两个长度为2的段查表C [ 2 ] nil C[2] \text{nil}C[2]nil两个都是含义都不切割直接卖出最优切割方案切割成2英寸 2英寸 2英寸总收益4 4 4 12 4 4 4 1244412元 ✅回溯算法伪代码算法Print-Optimal-Cut(C[], k) 输入切割点数组C[]钢条长度k 输出打印最优切割方案 1. if C[k] nil then 2. print 长度为k的钢条不切割直接卖出 3. else 4. i C[k] 5. print 在位置i切割得到长度为i和k-i的两段 6. Print-Optimal-Cut(C, i) // 递归处理左段 7. Print-Optimal-Cut(C, k-i) // 递归处理右段 8. end if⚠️ 常见错误与注意事项错误1忘记考虑不切割的情况错误做法# 错误只考虑切割忘记可以直接卖出R[k]max(R[i]R[k-i]foriinrange(1,k))正确做法# 正确同时考虑不切割和切割R[k]max(P[k],max(R[i]R[k-i]foriinrange(1,k)))为什么重要有时候不切割直接卖出可能比切割更优。错误2没有利用对称性优化错误做法# 错误尝试所有切割位置foriinrange(1,k):# 计算 R[i] R[k-i]正确做法# 正确利用对称性只需考虑 i ≤ k/2foriinrange(1,k//21):# 计算 R[i] R[k-i]为什么重要切割成i ii和k − i k-ik−i与切割成k − i k-ik−i和i ii是等价的可以减少一半的计算量。 算法复杂度分析时间复杂度分析外层循环长度k kk从 2 到n nn共n − 1 n-1n−1次内层循环切割位置i ii从 1 到⌊ k / 2 ⌋ \lfloor k/2 \rfloor⌊k/2⌋平均约k / 4 k/4k/4次总时间复杂度∑ k 2 n ⌊ k / 2 ⌋ O ( n 2 ) \sum_{k2}^{n} \lfloor k/2 \rfloor O(n^2)∑k2n⌊k/2⌋O(n2)递推关系T ( n ) O ( n 2 ) T(n) O(n^2)T(n)O(n2) 拓展思考为什么不能用贪心法局部最优不等于全局最优。例如可能短段的单价更高但最优方案可能是切割成长段。为什么时间复杂度是O ( n 2 ) O(n^2)O(n2)两层嵌套循环长度和切割位置。实际应用资源分配如何将有限资源分配给不同项目以最大化收益投资组合如何分配资金到不同投资项目生产计划如何安排生产以最大化利润与矩阵链乘法的对比相似点都是动态规划都需要记录最优值和最优解不同点矩阵链乘法是O ( n 3 ) O(n^3)O(n3)钢条切割是O ( n 2 ) O(n^2)O(n2)记忆口诀钢条切割用DP两个表格要记牢R表记录最优值C表回溯找方案自底向上O(n²)最大收益轻松算