当前位置：首页 > news >正文

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

news 2026/4/15 0:23:23

题目描述（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; }