这是一道很经典的题目。
dp状态的确定和推导都比较难想，但如果见多了，就熟了。
这题难点在于你扎气球时不知道左右两边最近的没扎的气球是谁。
既然不知道，那就以左右气球作为状态的坐标。
dp[i][j]的状态表示以左右两个端点i, j 为边界（不扎边界）能得到的最大金币。
由于状态定义是不扎边界，所以里面最后一个扎的气球k一定是和第i个气球和第j个气球相乘
dp[i][j] = Max_k (nums[k] * nums[i] * nums[j] + dp[j][k] + dp[k][i] for k from i to j;
代码如下。这道题十分经典，一定要熟练掌握
public int maxCoins(int[] nums) {
int[] nums2 = new int[nums.length + 2];
Arrays.fill(nums2, 1);
for (int i = 0; i < nums.length; i++) {
nums2[i + 1] = nums[i];
}
int N = nums2.length;
int[][] dp = new int[N][N];
//dp[i][j] 从以ij为最后两个气球能拿到的最大金币
for (int i = 0; i < N; i++) {
for (int j = i ; j >= 0; j--) {
if (i == j || j + 1 == i) {
dp[i][j] = 0;
dp[j][i] = 0;
} else {
int localMax = 0;
for (int k = i - 1; k > j; k--) {
localMax = Math.max(localMax,
dp[j][k] + dp[k][i] + nums2[k] * nums2[i] * nums2[j]);
}
dp[i][j] = localMax;
dp[j][i] = localMax;
}
}
}
return dp[0][N - 1];
}
