这道题是区间dp问题
不能正着来,要反着来,因为最后肯定只剩一个气球,所以最后一次的收益是固定的
dp[i][j]表示从区间(i,j)获得的最大收益,只戳中间,i和j不戳,假设在这个区间中有一个k,k是最后一个要戳的气球,那么最后一次的收益就是arr[i]*arr[k]*arr[j],根据这个k,(i,j)这个区间被分成两段,一段是(i,k),一段是(k,j),所以现在完成了状态转换,dp[i][j] = dp[i][k] + dp[k][j] + arr[i]*arr[k]*arr[j]
初始化阶段,我们需要在数组的两段加上1
class Solution { public int maxCoins(int[] nums) { int n = nums.length; // 两边补1 int[] arr = new int[n + 2]; arr[0] = 1; arr[n + 1] = 1; for (int i = 0; i < n; i++) { arr[i + 1] = nums[i]; } int[][] dp = new int[n + 2][n + 2]; // len 是区间长度 for (int len = 3; len <= n + 2; len++) { for (int i = 0; i + len - 1 < n + 2; i++) { int j = i + len - 1; // 枚举最后一个戳破的气球 for (int k = i + 1; k < j; k++) { dp[i][j] = Math.max( dp[i][j], dp[i][k] + dp[k][j] + arr[i] * arr[k] * arr[j] ); } } } return dp[0][n + 1]; } }
