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];
        
    }
};