动态规划——Burst Ballons

动态规划——Burst Ballons"/>

动态规划——Burst Ballons

动态规划——Burst Ballons

前言

在这道题之前 我们需要先会下面一题

关于矩阵连乘的最小次数

对于矩阵 A 1 , A 2 , ⋯ , A N A_1,A_2,\cdots,A_N A1​,A2​,⋯,AN​，其中 A i , A i + 1 A_i,A_{i+1} Ai​,Ai+1​是可乘的矩阵，对于这N个矩阵，要使其连乘的次数最小。

考虑采用分治的做法，把求解N个矩阵连乘的问题分解成N-1、N-2…2个矩阵的相乘，在每个区间内再进行划分，每次都找到使得乘积最少的分割点，为了提高效率，我们可以采用自底向上动态规划的方法

void matrixchain(int p[],int size)
{int m[SIZE][SIZE];//i到j的矩阵最小的乘积次数int s[SIZE][SIZE];memset(m, 0, sizeof(m));int r, i, j, k;for (r = 2; r <= size; r++){for (i = 1; i <= size - r + 1; i++){j = i + r - 1;m[i][j] = m[i + 1][j] + p[i - 1]*p[i]*p[j];s[i][j] = i;for (k = i + 1; k < j; k++){int temp = m[i][k] + m[k + 1][j] + p[i-1] * p[k] * p[j];if (temp < m[i][j]){m[i][j] = temp;s[i][j] = k;}}}}
}

其中比较重要的两点

m[i][j] = m[i + 1][j] + p[i - 1]*p[i]*p[j];//这个初始化非常nice!
s[i][j] = i;//初始化分割点i到点j  (i,j)=k

题目描述

You are given n balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it represented by an array nums. You are asked to burst all the balloons.

If you burst the ith balloon, you will get nums[i - 1] * nums[i] * nums[i + 1] coins. If i - 1 or i + 1 goes out of bounds of the array, then treat it as if there is a balloon with a 1 painted on it.

Return the maximum coins you can collect by bursting the balloons wisely.

解题思路

如果我们正向来看，每删除一个气球之后都会使得两边得气球靠近，这样不方便计算，所以我们可以倒过来看待，我们在两个气球之间插入一个气球，而且最重要得是利用(i,j)开区间来表示i到j区间戳破气球得最大值，而对于此种情况可以用,(i,j)=(i,k)+(k,j)+i*j*k来表示，因为这里相当于是(i,k)和(k,j)中间得气球已经刺破了！

下面来考虑区间分配的问题。首先是关于区间的长度，我们可以发现由于是开区间，所以区间长度至少要是3，因为如果区间长度是2，其实不存在选择的问题，而对于接下来一层的i应当是从0到n-1,j应当是i+r-1到n+1

下面是代码实现

class Solution {
public:int maxCoins(vector<int>& nums) {int size = nums.size();int res[size + 2][size + 2];int val[size + 2];for (int i = 1; i <= size; i++)val[i] = nums[i - 1];memset(res,0,sizeof(res));    int r, i, j, k;val[0] = 1;val[size + 1] = 1;for (r = 3; r <= size + 2; r++){for (i = 0; i <=size-r+2 ; i++){j = i + r - 1;for (k = i + 1; k < j; k++){int temp = res[i][k] + res[k][j] + val[i] * val[k] * val[j];res[i][j] = max(res[i][j], temp);}}}return res[0][size+1];}
};

或者可以考虑直接从后往前搜

class Solution {
public:int maxCoins(vector<int>& nums) {int size = nums.size();int res[size + 2][size + 2];int val[size + 2];for (int i = 1; i <= size; i++)val[i] = nums[i - 1];int r, i, j, k;val[0] = 1;val[size + 1] = 1;memset(res, 0, sizeof(res));for (i=size-1;i>=0 ; i--){for (j = i+2; j <=size+1 ; j++){for (k = i + 1; k < j; k++){int temp = res[i][k] + res[k][j] + val[i] * val[k] * val[j];res[i][j] = max(res[i][j], temp);}}}return res[0][size+1];}
};