DP solution with detailed text and video explanation.
LeetCode 312. Burst Balloons\n### Note\nIf you prefer video over text, please check out this link: https://www.youtube.com/watch?v=o3-PUPXiVfI\nwhich has the sa
## LeetCode 312. Burst Balloons\n### Note\nIf you prefer video over text, please check out this link: https://www.youtube.com/watch?v=o3-PUPXiVfI\nwhich has the same content as follows.\n### Explanation\n```java\nindex:      0   1   2   3\n          +---------------+\nnums:   1 | 3 | 1 | 5 | 8 | 1\n          +---------------+\n          \n// It may be easier to figure out the recurrence relation by looking at the last step.\n// At the last step, you only have one ballon (3, 1, 5 or 8) to burst, right?\n// So let\'s have something like opt(END) to denote max coins we can get at the end,\n// we know this opt(END) must come from one of the above 4 cases (by bursting 3, 1, 5 or 8)\n\n// So it seems like a good idea to use opt(i, j) to represent the max coins we can get from bursting balloons[i, j],\n// let\'s change opt(END) to opt(i, j) accordingly\nopt(0, 3) = max(\n    // If 3 is the last ballon, this means balloons[1, 5, 8] have been burst already, \n    // since we don\'t know the max coins we got by bursting[1, 5, 8], we\'ll\n    // use opt(1, 3) to denote max coins we can get by bursing balloons from 1 to 3, which is [1, 5, 8]\n    1 * 3 * 1 + opt(1, 3),\n    // Similarily, we have\n    1 * 1 * 1 + opt(0, 0) + opt(2, 3),\n    1 * 5 * 1 + opt(0, 1) + opt(3, 3),\n    1 * 8 * 1 + opt(0, 2)    \n    )\n\n// You may have figured out the recurrence relation from the above equation, if not,\n// let\'s look at how we\'ll calculate opt(1, 3)\n// Similar to the above equation, \nopt(1, 3) = max(\n    3 * 1 * 1 + opt(2, 3),\n    3 * 5 * 1 + opt(1, 1) + opt(3, 3),\n    3 * 8 * 1 + opt(1, 2)\n    )\n\n// Thus, we have\n>> state: \nopt[i][j] denotes the max coins we can get by bursting balloons[i, j]\n\n>> recurrence relationship:\nfor k from i to j\nmax(\n    // Edge cases are not considered in the below equation!\n    nums[i - 1] * nums[k] * nums[j + 1] + opt[i][k - 1] + opt[k + 1][j]\n)\n```\n### Code\n```java\nclass Solution {\n    public int maxCoins(int[] nums) {\n        int N = nums.length;\n        if(N == 0) return 0;\n\n        int[][] opt = new int[N][N];\n\n        for(int len = 0; len < N; ++len){\n            for(int i = 0; i + len < N; ++i){\n                int j = i + len;\n                for(int k = i; k <= j; ++k){\n                    // numbers on left ballon and right ballon.\n                    int left_num = i == 0 ? 1 : nums[i - 1];\n                    int right_num = j == N - 1 ? 1 : nums[j + 1];\n\n                    // left opt and right opt\n                    int left_opt = k == i ? 0 : opt[i][k - 1];\n                    int right_opt = k == j ? 0 : opt[k + 1][j];\n\n                    opt[i][j] = Math.max(\n                        opt[i][j], \n                        left_num * nums[k] * right_num + left_opt + right_opt);\n                }\n            }\n        }\n\n        return opt[0][N - 1];\n    }\n}\n```\n\n\n\n\n\n\n\n\n\n\n\'
[]