记忆化搜索

class Solution {public int[][] rec;//每个位置记录该区间填充满气球的最大硬币数public int[] val;//用于设置边界气球public int maxCoins(int[] nums) {int n = nums.length;//填充val数组val = new int[n + 2];for(int i = 1; i <= n; i++){val[i] = nums[i-1];}val[0]=val[n+1] = 1;//设置边界气球//初始化rec数组rec = new int[n+2][n+2];for(int i = 0; i < n+2; i++) {Arrays.fill(rec[i],-1);}return solve(0,n+1);//返回(0,n+1)之间填充满气球的最大硬币数}private int solve(int left, int right){if(left >= right -1){//区间内没有气球return 0;}if(rec[left][right] != -1){//防止重复计算return rec[left][right];}//遍历区间内所有的气球，把每个气球当作中间气球，最后记录最大值for(int i = left+1; i < right; i++){int sum = val[left] * val[i] * val[right];sum += solve(left,i) + solve(i,right);rec[left][right] = Math.max(rec[left][right],sum);}return rec[left][right];}
}

动态规化

动态规化与上面方法类似，从自顶向下变为了自底向上

class Solution {public int maxCoins(int[] nums) {int[][] rec;//每个位置记录该区间填充满气球的最大硬币数int[] val;//用于设置边界气球int n = nums.length;//填充val数组val = new int[n + 2];for(int i = 1; i <= n; i++){val[i] = nums[i-1];}val[0]=val[n+1] = 1;//设置边界气球//初始化rec数组rec = new int[n+2][n+2];for(int i = 1; i <=n+1; i++){for(int j = i - 2; j >= 0; j--){for(int k = j + 1; k < i; k++){int sum = val[j] * val[k] * val[i];sum += rec[j][k]+ rec[k][i];rec[j][i] = Math.max(sum,rec[j][i]);}}}return rec[0][n+1];}
}

官方题解