解法一：记忆化搜索

参见官方题解：https://leetcode-cn.com/problems/burst-balloons/solution/chuo-qi-qiu-by-leetcode-solution/

  1. class Solution {
  2.     // ans[left][right]表示开区间(i, j)内的气球都填满后得到的最大硬币数
  3.     private int[][] ans;
  4.     // val[i]表示第i个位置上的值, 左右边界均为1
  5.     private int[] val;
  7.     public int maxCoins(int[] nums) {
  8.         int n = nums.length;
  9.         val = new int[n + 2];
  10.         for (int i = 0; i < n; ++i) {
  11.             val[i + 1] = nums[i];
  12.         }
  13.         val[0] = val[n + 1] = 1;
  14.         ans = new int[n + 2][n + 2];
  15.         for (int[] i : ans) {
  16.             Arrays.fill(i, -1);
  17.         }
  18.         return solve(0, n + 1);
  19.     }
  21.     private int solve(int left, int right) {
  22.         if (left >= right - 1) {
  23.             return 0;
  24.         }
  25.         if (ans[left][right] != -1) {
  26.             return ans[left][right];
  27.         }
  28.         for (int i = left + 1; i < right; ++i) {
  29.             ans[left][right] = Math.max(ans[left][right], solve(left, i) + solve(i, right) + val[left] * val[i] * val[right]);
  30.         }
  31.         return ans[left][right];
  32.     }
  33. }

解法二：动态规划

理解官方题解并实现了第一种解法后，修改其形式。记忆化搜索的方式在求解高阶问题的过程中递归地求解低阶问题，用数组保存低阶问题的解，因此完全可以修改成动态规划的形式，先求解区间小的低阶问题，再求解高阶问题。

  1. class Solution {
  2.     // ans[left][right]表示开区间(i, j)内的气球都填满后得到的最大硬币数
  3.     private int[][] ans;
  4.     // val[i]表示第i个位置上的值, 左右边界均为1
  5.     private int[] val;
  7.     public int maxCoins(int[] nums) {
  8.         int n = nums.length;
  9.         val = new int[n + 2];
  10.         for (int i = 0; i < n; ++i) {
  11.             val[i + 1] = nums[i];
  12.         }
  13.         val[0] = val[n + 1] = 1;
  14.         ans = new int[n + 2][n + 2];
  15.         for (int len = 2; len <= n + 1; ++len) {
  16.             for (int left = 0, right = left + len; right <= n + 1; ++left, ++right) {
  17.                 for (int mid = left + 1; mid < right; ++mid) {
  18.                     ans[left][right] = Math.max(ans[left][right], ans[left][mid] + ans[mid][right] + val[left] * val[mid] * val[right]);
  19.                 }
  20.             }
  21.         }
  22.         return ans[0][n + 1];
  23.     }
  24. }