Hard DP part 3

LC 312

https://leetcode.com/problems/burst-balloons/

The solution is from Errichto.

The critical part is to think about the process reversely.

time complexity O(N³)

space O(N²)

https://youtu.be/yYYvva80AFM

Bottom up

class Solution {
public:
int maxCoins(vector<int>& A) {
if(A.empty())return 0;
const int n=A.size();
vector<vector<int>> dp(n, vector<int>(n));
for (int L=n-1;L>=0;--L)
for (int R=L;R<n;++R)
for (int i=L;i<=R;++i)
dp[L][R] = max(dp[L][R],
(L-1<0?1:A[L-1])*A[i]*(R+1>=n?1:A[R+1])+
(L>i-1?0:dp[L][i-1])+
(i+1>R?0:dp[i+1][R])
);
return dp[0][n-1];
}
};

Top down

int memo[510][510];
class Solution {
public:
int dp(vector<int>& nums, int i, int j){
const int n = nums.size();
if (i > j) return 0;
if (i == j) return (i - 1 >= 0? nums[i-1]:1)*nums[i]*(i +1 < n ? nums[i+1]: 1) ;
if (memo[i][j] != -1)return memo[i][j];
int ret = INT_MIN;
for (int k = i; k <= j; ++k){
int thisret = (i - 1 >= 0? nums[i-1]:1)*nums[k]*(j +1 < n ? nums[j+1]: 1) +
dp(nums, i, k -1) +
dp(nums, k +1, j);
ret = max(ret, thisret);
}
return memo[i][j] = ret;
}
int maxCoins(vector<int>& nums) {
const int n = nums.size();
memset(memo, -1, sizeof memo);
return dp(nums, 0, n - 1);
}
};

1155. Number of Dice Rolls With Target Sum

https://leetcode.com/problems/number-of-dice-rolls-with-target-sum/

Be careful, set the ways[0] to 1 as it can gaurantee the base case is correct.

If you have questions, please think a 6 faces dice only roll once

ways = {1,0,0,0,0,0,0}

then if we roll 1, we will get the following, it is correct.

new_ways = {0,1,0,0,0,0,0}

if we roll 2, we will update it as

new_ways = {0,1,1,0,0,0,0}

keep on going, we will have

new_ways = {0,1,1,1,1,1,1}

If we have a second dice, let roll 1, we will have

new_ways = {0,1,2,2,2,2}

and roll 2, we will have

new_ways = {0,1,2,3,3,3}

//24ms
const int mod = 1e9 + 7;
class Solution {
public:
int numRollsToTarget(int d, int f, int target) {
vector<int> ways(target+1);
ways[0] = 1; //empty will have sum of 0
for(int rep=0;rep<d;++rep){
vector<int> new_ways(target+1);
for(int i=0;i<=target;++i){
for(int j=1;j<=f;++j){
if(i+j<=target){
int temp = new_ways[i+j] + ways[i];
if(temp>=mod)temp-=mod;
new_ways[i+j] = temp;
}
}
}
ways = new_ways;

}
return ways[target];

}
};

One beautify part to improve the solution of above code is using presum.

// 8ms
const int mod = 1e9 + 7;
void add(int &a, int b){
a +=b;
if(a>=mod)a-=mod;
}
class Solution {
public:
int numRollsToTarget(int d, int f, int target) {
vector<int> ways(target+1);
ways[0] = 1; //empty will have sum of 0
for(int rep=0;rep<d;++rep){
for (int i=1;i<=target;++i){
add(ways[i],ways[i-1]);
}
vector<int> new_ways(target+1);
for (int i=1;i<=target;++i){
new_ways[i] = (i-1>=0?ways[i-1]:0)-(i-f-1>=0?ways[i-f-1]:0);
if (new_ways[i]<0) new_ways[i]+=mod;
}
/*
for(int i=0;i<=target;++i){
for(int j=1;j<=f;++j){
if(i+j<=target){
int temp = new_ways[i+j] + ways[i];
if(temp>=mod)temp-=mod;
new_ways[i+j] = temp;
}
}
}
*/
ways = new_ways;

}
return ways[target];

}
};

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store