LeetCode-312. Burst Balloons [C++][Java]

LeetCode-312. Burst Balloonshttps://leetcode.com/problems/burst-balloons/

You are given n balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it represented by an array nums. You are asked to burst all the balloons.

If you burst the ith balloon, you will get nums[i - 1] * nums[i] * nums[i + 1] coins. If i - 1 or i + 1 goes out of bounds of the array, then treat it as if there is a balloon with a 1 painted on it.

Return the maximum coins you can collect by bursting the balloons wisely.

Example 1:

Input: nums = [3,1,5,8]
Output: 167
Explanation:
nums = [3,1,5,8] --> [3,5,8] --> [3,8] --> [8] --> []
coins =  3*1*5    +   3*5*8   +  1*3*8  + 1*8*1 = 167

Example 2:

Input: nums = [1,5]
Output: 10

Constraints:

n == nums.length1 <= n <= 3000 <= nums[i] <= 100

class Solution {
public:
    vector> dp;
    int solve(int i,int j,vector& nums){
        if (i + 1 == j) {return 0;}
        if (dp[i][j] != -1) {return dp[i][j];}
        int ans = 0;
        for (int k = i + 1; k < j; k++){
            if (dp[i][k] == -1) {dp[i][k] = solve(i, k, nums);}
            if (dp[k+1][j] == -1) {dp[k][j] = solve(k, j, nums);}
            ans = max(ans, dp[i][k] + dp[k][j] + nums[i] * nums[k] * nums[j]);
        }
        return dp[i][j] = ans;
    }

    int maxCoins(vector& nums) {
        nums.insert(nums.begin(), 1);
        nums.push_back(1);
        int n = nums.size();
        dp = vector>(n, vector(n, -1));
        return solve(0, n-1, nums);
    }
};

class Solution {
public:
    int maxCoins(vector& nums) {
       int n = nums.size();
       vector> dp(n, vector(n));
       for(int g = 0; g < n; g++){
           for(int i = 0, j = g; j 
【Java】 
class Solution {
    public int maxCoins(int[] nums) {
        int n = nums.length;
        if (n==0) return 0;
        if (n==1) return nums[0];
        int[][] memo = new int[n][n];
        for (int len=1; len<=n; len++) {
            for (int st=0,end=st+len-1; end