动态规划专题(05)：区间动态规划实践（乘法游戏）

题目描述POJ1651乘法游戏是用一些牌来玩的在每张牌上都有一个正整数。玩家从一行牌中取出一张牌得分的数量等于所取牌上的数字与左右两张牌上的数字的乘积。不允许取出第一张和最后一张牌。经过最后一步后只剩下两张牌。玩牌的目标是把得分的总数降到最低。例如若一行牌包含数字 10、1、50、20、5则若玩家先拿出一张 1然后拿出 20 和 50 的牌得分便是 10×1×50 50×20×5 10×50×5 500 5000 2500 8000。若他按相反的顺序拿牌即 50、20、1则得分是 1×50×20 1×20×5 10×1×5 1000 100 50 1150。输入第 1 行包含牌的数量 n3≤n≤100第 2 行包含 1100 的 n 个整数表示牌上的数字。输出单行输出玩牌的最小分数。1.1 问题概述乘法游戏是一个经典的区间动态规划问题。给定一行牌每张牌上有一个正整数。玩家需要依次取出中间的牌每次取牌得分为该牌数字与左右两张牌数字的乘积。最终剩下第一张和最后一张牌目标是使总得分最小。1.2 问题形式化设有 n 张牌数字序列为 a[1..n]。每次操作是选择一个索引 k (1 k n)取出 a[k]得分为 a[k-1] × a[k] × a[k1]。之后序列长度减1原 a[k] 位置被移除其左右元素相邻。二、问题理解2.1 关键理解要点操作顺序影响结果不同的取牌顺序会导致不同的总得分最后剩下两张牌即第一张和最后一张牌始终保留区间独立性当确定一个区间和最后取出的牌时问题可以分解为子问题2.2 示例分析示例10, 1, 50, 20, 5顺序1取1→取20→取5010×1×50 50050×20×5 500010×50×5 2500总分8000顺序2取50→取20→取11×50×20 10001×20×5 10010×1×5 50总分1150三、算法设计与实现3.1 基础实现方法算法思路使用区间DP定义状态dp[i][j]表示区间 [i, j] 内i 和 j 是保留的牌取完中间所有牌的最小得分状态转移dp[i][j] min(dp[i][k] dp[k][j] a[i]×a[k]×a[j])其中 i k j初始条件dp[i][i1] 0区间内无牌可取代码实现#include iostream #include vector #include climits using namespace std; // 基础版朴素区间DP long long matrixChainMinScoreBasic(const vectorint cards) { int n cards.size(); vectorvectorlong long dp(n, vectorlong long(n, LLONG_MAX)); // 初始化 for (int i 0; i n-1; i) { dp[i][i1] 0; // 相邻两张牌中间无牌可取 } // 区间长度从2开始实际是包含牌数len1 for (int len 2; len n; len) { for (int i 0; i len n; i) { int j i len; // 枚举最后取出的牌k for (int k i1; k j; k) { long long score dp[i][k] dp[k][j] (long long)cards[i] * cards[k] * cards[j]; if (score dp[i][j]) { dp[i][j] score; } } } } return dp[0][n-1]; } int main() { int n; cout 输入牌的数量: ; cin n; vectorint cards(n); cout 输入牌上的数字: ; for (int i 0; i n; i) { cin cards[i]; } long long result matrixChainMinScoreBasic(cards); cout 最小分数: result endl; return 0; }3.2 优化实现方法优化思路提前计算乘积减少重复计算减少边界检查优化循环结构使用更紧凑的数据结构根据实际情况选择代码实现#include iostream #include vector #include climits #include algorithm using namespace std; // 优化版改进的区间DP long long matrixChainMinScoreOptimized(const vectorint cards) { int n cards.size(); vectorvectorlong long dp(n, vectorlong long(n, 0)); // 初始化所有dp[i][i1] 0 // 自底向上计算 for (int len 2; len n; len) { // 区间长度 for (int i 0; i len n; i) { // 区间起点 int j i len; // 区间终点 dp[i][j] LLONG_MAX; // 优化提前计算固定乘积 long long baseProduct (long long)cards[i] * cards[j]; for (int k i 1; k j; k) { long long current dp[i][k] dp[k][j] baseProduct * cards[k]; if (current dp[i][j]) { dp[i][j] current; } } } } return dp[0][n-1]; } int main() { int n; cout 输入牌的数量: ; cin n; vectorint cards(n); cout 输入牌上的数字: ; for (int i 0; i n; i) { cin cards[i]; } long long result matrixChainMinScoreOptimized(cards); cout 最小分数: result endl; return 0; }四、测试数据与验证4.1 测试数据组#include iostream #include vector #include climits using namespace std; // 测试函数 void runTests() { // 测试数据1题目示例 vectorint test1 {10, 1, 50, 20, 5}; cout 测试1: {10, 1, 50, 20, 5} endl; cout 预期结果: 1150 endl; // 测试数据2简单情况 vectorint test2 {1, 2, 3}; cout \n测试2: {1, 2, 3} endl; cout 预期结果: 6 (因为只有一种取法: 1×2×36) endl; // 测试数据3递增序列 vectorint test3 {2, 4, 6, 8}; cout \n测试3: {2, 4, 6, 8} endl; cout 计算最小分数... endl; // 测试数据4随机序列 vectorint test4 {5, 3, 8, 2, 9, 4}; cout \n测试4: {5, 3, 8, 2, 9, 4} endl; cout 计算最小分数... endl; // 测试数据5边界情况 vectorint test5 {100, 100, 100, 100, 100}; // 全部相同 cout \n测试5: {100, 100, 100, 100, 100} endl; cout 计算最小分数... endl; } int main() { runTests(); return 0; }4.2 完整测试程序#include iostream #include vector #include climits #include algorithm using namespace std; // 基础版 long long solveBasic(const vectorint cards) { int n cards.size(); vectorvectorlong long dp(n, vectorlong long(n, LLONG_MAX)); for (int i 0; i n-1; i) { dp[i][i1] 0; } for (int len 2; len n; len) { for (int i 0; i len n; i) { int j i len; for (int k i1; k j; k) { long long score dp[i][k] dp[k][j] (long long)cards[i] * cards[k] * cards[j]; if (score dp[i][j]) { dp[i][j] score; } } } } return dp[0][n-1]; } // 优化版 long long solveOptimized(const vectorint cards) { int n cards.size(); vectorvectorlong long dp(n, vectorlong long(n, 0)); for (int len 2; len n; len) { for (int i 0; i len n; i) { int j i len; dp[i][j] LLONG_MAX; long long base (long long)cards[i] * cards[j]; for (int k i1; k j; k) { long long current dp[i][k] dp[k][j] base * cards[k]; if (current dp[i][j]) { dp[i][j] current; } } } } return dp[0][n-1]; } int main() { cout POJ1651 乘法游戏测试程序 endl; // 多组测试数据 vectorvectorint testCases { {10, 1, 50, 20, 5}, // 示例 {1, 2, 3}, // 最小情况 {2, 4, 6, 8}, // 递增序列 {5, 3, 8, 2, 9, 4}, // 随机序列 {100, 100, 100, 100, 100} // 边界情况 }; vectorlong long expected {1150, 6, 0, 0, 0}; // 0表示需要计算 for (int i 0; i testCases.size(); i) { cout \n 测试用例 i1 endl; cout 牌序列: ; for (int num : testCases[i]) { cout num ; } cout endl; long long resultBasic solveBasic(testCases[i]); long long resultOptimized solveOptimized(testCases[i]); cout 基础版结果: resultBasic endl; cout 优化版结果: resultOptimized endl; if (resultBasic resultOptimized) { cout ✓ 结果一致 endl; } else { cout ✗ 结果不一致 endl; } if (expected[i] ! 0 resultBasic expected[i]) { cout ✓ 与预期结果一致 endl; } else if (expected[i] ! 0) { cout ✗ 与预期结果不一致 endl; } } // 用户自定义测试 cout \n 自定义测试 endl; int n; cout 输入牌的数量: ; cin n; if (n 3 n 100) { vectorint cards(n); cout 输入 n 个数字: ; for (int i 0; i n; i) { cin cards[i]; } long long result solveOptimized(cards); cout 最小分数: result endl; } else { cout 牌的数量必须在3~100之间 endl; } return 0; }五、使用技巧5.1 算法理解技巧联想矩阵链乘这个问题本质上是矩阵链乘问题的变种区间DP模板掌握标准的区间DP写法最后操作思想考虑最后取出的牌将问题分解为两个子问题5.2 实现技巧循环顺序先枚举区间长度再枚举起点初始化正确初始化边界条件数据类型使用long long防止溢出六、注意事项6.1 易错点数组下标注意从0开始还是从1开始边界条件dp[i][i1]必须初始化为0循环范围区间长度从2开始k的范围是(i1)到(j-1)6.2 性能考虑时间复杂度O(n³)n≤100时可以接受空间复杂度O(n²)溢出问题最大可能分数为100×100×100×10010⁸但多次累加可能超过int范围七、问题避免7.1 常见错误错误的状态定义dp[i][j]表示区间[i,j]而不是[i,j]之间的牌错误的转移方程忘记加上最后操作的分数初始化错误没有正确初始化长度为2的区间7.2 调试建议先用小数据测试打印DP表格验证对比暴力搜索的结果八、总结8.1 算法特点经典区间DP问题类似矩阵链乘时间复杂度O(n³) 对于 n≤100 足够空间复杂度O(n²) 可以优化为O(n)但实现复杂8.2 应用场景动态规划教学示例区间DP入门题目算法竞赛基础题目8.3 扩展思考如何输出具体的最优操作序列如果牌的数量更大如n≤500如何优化如果得分计算方式不同如何修改通过本文档的学习读者应该能够理解乘法游戏问题的本质掌握区间DP的解决方法并能够根据实际情况选择合适的实现方式。关键是要理解最后操作的思想将大问题分解为子问题这是解决许多区间DP问题的核心思路。