力扣312-戳气球区间dp_力扣 区间dp

312戳气球

[3,1,5,8]
维护一个dp矩阵，dp[i][j]表示从i到j能够获得的最大硬币数量，
定义子问题，dp[i][j] 的最大值等于max( dp[i][k] + dp[k][j]) , i<k<j ;
正向思考，从左至右分别算dp[i][j], 左边被戳破的气球用1代替

3 -> 1*3*1 = 3
1 -> 1*1*5 = 5
5 -> 1*5*8 = 40
8 –> 1*1*8 = 8
Sum = 3+5+40+8 = 56,
按顺序点不能获取最大值，如先点 1
3*1*5 = 15 再点5
3*5*8 = 120， 再点3
1*3*8 = 24，最后点 8
1*8*1 = 8
Sum = 15+120+24+8 = 167

[3,1,5] 先戳破1
由此，dp[i][k]dp[k][j]
为什么k是最后一个被戳破的气球？[3,1,5] 子问题的独立性，如果是先戳破1,[3,5]两个子问题并不独立， 最后戳破1 ，那么[3],[5]只和1有关联。

dp[i][j] = dp[i][k]+dp[k][j]+nums[i]*nums[k]*nums[j], 且i<k<j

注意, dp[i][j] 用到了 dp[i][k] 和 dp[k][j]两个子区间，所以要先把这两个子区间的dp值算出来， 从后往前计算
dp[0][5]=dp[0][i]+dp[i][5]+nums[0]*nums[i]*nums[5];
dp[0][2]=nums[0]*nums[1]*nums[2]+dp[0][1]+dp[1][2]

#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    int maxCoins(vector<int>& nums) {
    	int n = nums.size();
		nums.insert(nums.begin(),1);
		nums.push_back(1);
		
		vector<vector<int> > dp(n+2, vector<int>(n+2,0));
		n = nums.size();					
		// //因为会用到dp[k][j],所以这里倒序遍历i值
		for(int i=n-2;i>=0;i--){
			for(int j=i+1;j<n;j++){	//end-start>=2
				for(int k=i+1;k<j;k++){
					dp[i][j] = max(dp[i][j],dp[i][k]+dp[k][j]+nums[i]*nums[j]*nums[k]);
				}
			}
		}
		return dp[0][n-1];
    }
};

int main()
{	
	int arr[] = {3,1,5,8};
	vector<int> v(arr,arr+4);
	Solution s;
	cout << s.maxCoins(v) << endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

参考题解：
[1]https://qoogle.top/leetcode-312-burst-balloons/
[2]https://leetcode-cn.com/problems/burst-balloons/solution/chuo-qi-qiu-dong-tai-gui-hua-wen-ti-by-lidada/