[Java] O(n^3) DP clean code with explanation
If you have some experience solving DP problems, you\'ll quickly realize that it is a DP problem.\n\nLet dp[i][j] =maximum value we can obtain by bursting all b
If you have some experience solving DP problems, you\'ll quickly realize that it is a DP problem.\n\nLet ```dp[i][j]``` =maximum value we can obtain by bursting all balloons from ```i``` to ```j``` given that balloons ```i-1``` and ```j+1``` are unburst.\n\nIf balloon ```k``` is the last to burst between ```i``` and ```j```, then ```dp[i][j]``` can be written as:\n```dp[i][j]``` = max value of ( ```dp[i][k-1] + nums[i-1] * nums[k] * nums[j+1] + dp[k+1][j]``` ) for all ```k``` where ```k``` goes from ```i``` to ```j```\n\nNote that ```dp[i][k-1]``` and ```dp[k+1][j]``` are independent subproblems of each other because balloon ```k``` exists when calculating either of them. Remember balloons in ```dp[i][k-1]``` and ```dp[k+1][j]``` get burst **before** balloon ```k``` so balloon ```k``` exists for them.\nThis is precisely why we have defined balloon ```k``` to be the **last** balloon to burst between ```i``` and ```j``` and **not the first**. If we had defined balloon ```k``` to be the first, then balloons ```k-1``` and ```k+1``` will become adjacent and then ```dp[i][k-1]``` and ```dp[k+1][j]``` subproblems will overlap.\n\nIn order to avoid lot of checks for valid indices in the code, we can copy ```nums``` into another array and prepend and append a balloon of cost 1 as stated in the problem. Then we can calculate ```dp[i][j]``` on 1-based ```i``` and ```j``` so that ```dp[1][n]``` gives the answer.\n\n```\npublic int maxCoins(int[] nums) {\n    int n = nums.length;\n    int[] A = new int[n + 2];\n    for(int i = 1; i <= n; i++) A[i] = nums[i-1];\n    A[0] = A[n + 1] = 1;\n    int[][] dp = new int[n + 2][n + 2];\n    for(int j = 1; j <= n; j++) {\n        for(int i = j; i >= 1; i--) {\n            for(int k = i; k <= j; k++) {\n                dp[i][j] = Math.max(dp[i][j], dp[i][k-1] + dp[k+1][j] + A[i-1] * A[k] * A[j+1]);\n            }\n        }\n    }\n    return dp[1][n];\n}\n```\n\nFYI: In case you\'re interested, code without creating another array:\n\n```\npublic int maxCoins(int[] nums) {\n    int n = nums.length;\n    int[][] dp = new int[n][n];\n    for(int j = 0; j < n; j++) {\n        for(int i = j; i >= 0; i--) {\n            for(int k = i; k <= j; k++) {\n                dp[i][j] = Math.max(dp[i][j], (k == i ? 0 : dp[i][k-1]) + (k == j ? 0 : dp[k+1][j]) + (i == 0 ? 1 : nums[i-1]) * nums[k] * (j == n-1 ? 1 : nums[j+1]));\n            }\n        }\n    }\n    return n == 0 ? 0 : dp[0][n-1];\n}\n```
['Dynamic Programming', 'Java']