算法设计与分析之戳气球问题【动态规划】

戳气球题目

有n个气球，编号为0到n-1，每个气球都有一个分数，存在nums数组中。每次戳气球i可以得到的分数为 nums[left] * nums[i] * nums[right]，left和right分别表示i气球相邻的两个气球。当i气球被戳爆后，其左右两气球即为相邻。要求戳爆所有气球，得到最多的分数。

备注：

1.你可以假设nums[-1] = nums[n] = 1。-1和n位置上的气球不真实存在，因此不能戳爆它们。

2.0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

代码具体实现

输出分数表和k表，求得最优解和最优方案：

备注：虽然最后追溯最优方案有点小问题，但是无伤大雅了。

#include
#include
#include
using namespace std;
#define N 100
int maxCoins(vector<int>& nums) {  //参数是用vector做的动态数组nums,也是初始问题 int n = nums.size();     //数组长度，其实也就是气球个数n（0~n-1一共是n个） vector<vector<int> > dp(n + 2, vector<int>(n + 2));     //构造动态二维dp[][]数组 vector<vector<int> > s(n + 2, vector<int>(n + 2));vector<int> points(n + 2);    //添加虚拟气球后改变问题的一维points[]数组 ，虚拟的2个气球是辅助功能，我们只需要戳两端中间的气球，即是开区间 points[0] = points[n + 1] = 1;  //题目给的条件0和n+1气球吹破为1for (int i = 1; i <= n; i++) {points[i] = nums[i - 1];    //改变问题后points[i]就应该等于原问题的nums[i-1],此处i从1开始到n结束，因为我们对points已经考虑过了0和n+1的 情况了，而nums是从0~n-1 }for (int i = n - 1; i >= 0; i--) {                  for (int j = i + 2; j <= n + 1; j++) {s[i][j] = i;for (int k = i + 1; k < j; k++) {     //穷举i到j之间的气球 ，iint sum = points[i] * points[k] * points[j];sum += dp[i][k] + dp[k][j];//dp[i][j] = max(dp[i][j], sum);if (sum > dp[i][j]) {dp[i][j] = sum;s[i][j] = k;}}}}cout << "k表：" << endl;for (int i = 0; i <= n + 1; i++) {for (int j = 0; j <= n + 1; j++) {cout.width(7);cout << s[i][j];}cout << endl;}cout << "分数表为：" << endl;for (int i = 0; i <= n + 1; i++) {for (int j = 0; j <= n + 1; j++) {cout.width(7);cout << dp[i][j];}cout << endl;}return dp[0][n + 1];//返回最大值，戳破0~n+1之间的气球 }
int main() {int n;cout << "请输入气球个数:" << endl;cin >> n;cout << "请输入各气球分数：" << endl;vector<int> nums(n);for (int i = 0; i < n; i++) {cin >> nums[i];}cout << "获得的最大分数为:" << maxCoins(nums);return 0;
}