DynamicProgrammingStriver/BurstBallonsPartitionDPLecture51.cpp at main · dhruvkej9/DynamicProgrammingStriver · GitHub

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <vector>
#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;
int solve1(int i,int j,vector<int>& a,vector<vector<int>> &dp)
{
	if(i > j) return 0;
	if(dp[i][j] != -1) return dp[i][j];
	int maxi = INT_MIN;
	for(int ind = i;ind <= j;ind++)
	{
		int cost = a[i-1]*a[ind]*a[j+1] +
				   solve1(i,ind - 1,a,dp) +
				   solve1(ind + 1,j,a,dp);
		maxi = max(maxi,cost);
	}
	return dp[i][j] = maxi;
}
int solve2(vector<int>& a)
{
	int n = a.size();
	a.emplace_back(1);
	a.emplace(a.begin(),1);
	vector<vector<int>> dp(n + 2,vector<int>(n + 2,0));
	for(int i = n;i >= 1;i--)
	{
		for(int j = 1;j <= n;j++)
		{   // j == n so size is n + 2
			if(i > j) continue;
			int maxi = INT_MIN;
			for(int ind = i;ind <= j;ind++)
			{
				int cost = a[i-1]*a[ind]*a[j+1] +
							dp[i][ind - 1] +
							dp[ind + 1][j];
				maxi = max(maxi,cost);
			}
			dp[i][j] = maxi;
		}
	}
	return dp[1][n];
}
int maxCoins(vector<int>& a)
{
	int n = a.size();
	// a.emplace_back(1);
	// a.emplace(a.begin(),1);
	// vector<vector<int>> dp(n + 1,vector<int>(n+1,-1));
	// return solve1(1,n,a,dp);
	return solve2(a);
}