题目描述

image.png

解题思路

参照🔗
dp[i][j]表示的是在i，j的区间中能获得硬币的最大数量，解释一下dp递推公式
image.png
在这个区间，最后一次随意戳爆一个气球，例如戳粉色的，那么其递推公式就为：
dp[i][j] = dp[i][k] + dp[k][j] + val[i] val[k] val[j]，为啥是val[i] val[k] val[j]？因为k表示是最后一个删除的气球，所以前面的都被全部删除了。

  1. public int maxCoins(int[] nums) {
  2.     int n = nums.length;
  3.     int[] newNums = new int[nums.length + 2];
  4.     newNums[0] = 1;
  5.     newNums[n + 1] = 1;
  6.     for (int i = 0; i < n; i++) {
  7.         newNums[i + 1] = nums[i];
  8.     }
  9.     int[][] dp = new int[n + 2][n + 2];
  11.     // 表示开区间长度
  12.     for (int len = 3; len <= n + 2; len++) {
  13.         // 开区间的最左边
  14.         for (int i = 0; i <= n + 2 - len; i++) {
  15.             int res = 0;
  16.             // 中间索引
  17.             for (int j = i + 1; j < i + len - 1; j++) {
  18.                 int left = dp[i][j];
  19.                 int right = dp[j][i + len - 1];
  20.                 res = Math.max(res, left + newNums[i] * newNums[j] * newNums[i + len - 1] + right);
  21.             }
  22.             dp[i][i + len - 1] += res;
  23.         }
  24.     }
  26.     return dp[0][n + 1];
  27. }