：区间动态规划实践（乘法游戏）)
题目描述（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 行包含牌的数量 n（3≤n≤100），第 2 行包含 1～100 的 n 个整数，表示牌上的数字。
输出：单行输出玩牌的最小分数。
1.1 问题概述
乘法游戏是一个经典的区间动态规划问题。给定一行牌，每张牌上有一个正整数。玩家需要依次取出中间的牌，每次取牌得分为该牌数字与左右两张牌数字的乘积。最终剩下第一张和最后一张牌，目标是使总得分最小。
1.2 问题形式化
设有 n 张牌，数字序列为 a[1..n]。每次操作是选择一个索引 k (1 < k < n)，取出 a[k]，得分为 a[k-1] × a[k] × a[k+1]。之后序列长度减1，原 a[k] 位置被移除，其左右元素相邻。
二、问题理解
2.1 关键理解要点
操作顺序影响结果：不同的取牌顺序会导致不同的总得分
最后剩下两张牌：即第一张和最后一张牌始终保留
区间独立性：当确定一个区间和最后取出的牌时，问题可以分解为子问题
2.2 示例分析
示例：10, 1, 50, 20, 5
顺序1：取1→取20→取50
10×1×50 = 500
50×20×5 = 5000
10×50×5 = 2500
总分：8000
顺序2：取50→取20→取1
1×50×20 = 1000
1×20×5 = 100
10×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][i+1] = 0（区间内无牌可取）
代码实现
#include <iostream> #include <vector> #include <climits> using namespace std; // 基础版：朴素区间DP long long matrixChainMinScoreBasic(const vector<int>& cards) { int n = cards.size(); vector<vector<long long>> dp(n, vector<long long>(n, LLONG_MAX)); // 初始化 for (int i = 0; i < n-1; i++) { dp[i][i+1] = 0; // 相邻两张牌，中间无牌可取 } // 区间长度从2开始（实际是包含牌数=len+1） for (int len = 2; len < n; len++) { for (int i = 0; i + len < n; i++) { int j = i + len; // 枚举最后取出的牌k for (int k = i+1; 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; vector<int> 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 vector<int>& cards) { int n = cards.size(); vector<vector<long long>> dp(n, vector<long long>(n, 0)); // 初始化：所有dp[i][i+1] = 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; vector<int> 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：题目示例 vector<int> test1 = {10, 1, 50, 20, 5}; cout << "测试1: {10, 1, 50, 20, 5}" << endl; cout << "预期结果: 1150" << endl; // 测试数据2：简单情况 vector<int> test2 = {1, 2, 3}; cout << "\n测试2: {1, 2, 3}" << endl; cout << "预期结果: 6 (因为只有一种取法: 1×2×3=6)" << endl; // 测试数据3：递增序列 vector<int> test3 = {2, 4, 6, 8}; cout << "\n测试3: {2, 4, 6, 8}" << endl; cout << "计算最小分数..." << endl; // 测试数据4：随机序列 vector<int> test4 = {5, 3, 8, 2, 9, 4}; cout << "\n测试4: {5, 3, 8, 2, 9, 4}" << endl; cout << "计算最小分数..." << endl; // 测试数据5：边界情况 vector<int> 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 vector<int>& cards) { int n = cards.size(); vector<vector<long long>> dp(n, vector<long long>(n, LLONG_MAX)); for (int i = 0; i < n-1; i++) { dp[i][i+1] = 0; } for (int len = 2; len < n; len++) { for (int i = 0; i + len < n; i++) { int j = i + len; for (int k = i+1; 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 vector<int>& cards) { int n = cards.size(); vector<vector<long long>> dp(n, vector<long 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 = i+1; 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; // 多组测试数据 vector<vector<int>> testCases = { {10, 1, 50, 20, 5}, // 示例 {1, 2, 3}, // 最小情况 {2, 4, 6, 8}, // 递增序列 {5, 3, 8, 2, 9, 4}, // 随机序列 {100, 100, 100, 100, 100} // 边界情况 }; vector<long long> expected = {1150, 6, 0, 0, 0}; // 0表示需要计算 for (int i = 0; i < testCases.size(); i++) { cout << "\n=== 测试用例 " << i+1 << " ===" << 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) { vector<int> 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][i+1]必须初始化为0
循环范围：
区间长度从2开始
k的范围是(i+1)到(j-1)
6.2 性能考虑
时间复杂度：O(n³)，n≤100时可以接受
空间复杂度：O(n²)
溢出问题：最大可能分数为100×100×100×100=10⁸，但多次累加可能超过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问题的核心思路。
