# 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}

`//24msconst 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.

`// 8msconst 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];            }};`

--

--

## More from Jimmy Shen

Data Scientist/MLE/SWE @takemobi

Love podcasts or audiobooks? Learn on the go with our new app.