记忆化搜索
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];
}
}