https://leetcode-cn.com/problems/burst-balloons/

范围上的尝试

  • int f（L, R）
    • 在arr [L, R]要气球全爆，返回最大分数（潜台词是L-1和R + 1位置的气球一定没爆）、
  • 那么主函数怎么调？
    • 数组开头补个1， 结尾补个1， （满足潜台词）然后永远不碰0位置和N + 1位置

image.png

  • 怎么整理可能性？谁是最后爆的气球 （整个过程始终都满足潜台词）

image.png

  1.  public int maxCoins(int[] nums) {
  2.      int N = nums.length;
  3.      int[] help = new int[N + 2];
  4.      help[0] = 1;
  5.      help[N + 1] = 1;
  6.      for (int i = 0; i < N; i++) {
  7.          help[i + 1] = nums[i];
  8.      }
  9.      return process(help, 1, N);
  10.  }
  12. private int process(int[] arr, int L, int R) {
  13.     if (L == R) { // 如果L ~ R范围内只有1个气球，直接打爆即可
  14.         return arr[L - 1] * arr[L] * arr[R + 1];
  15.     }
  16.     int max = Math.max(
  17.         process(arr, L + 1, R) + arr[L - 1] * arr[L] * arr[R + 1],
  18.         process(arr, L, R - 1) + arr[L - 1] * arr[R] * arr[R + 1]);
  19.     for (int i = L + 1; i < R; i++) {
  20.         max = Math.max(max,
  21.                        arr[L - 1] * arr[i] * arr[R + 1] + process(arr, L, i - 1)
  22.                        + process(arr, i + 1, R));
  23.     }
  24.     return max;
  25. }

  • 递归改动态规划

    1. public int maxCoins(int[] nums) {
    2.       int N = nums.length;
    3.       int[] help = new int[N + 2];
    4.       help[0] = 1;
    5.       help[N + 1] = 1;
    6.       for (int i = 0; i < N; i++) {
    7.           help[i + 1] = nums[i];
    8.       }
    9.       int[][] dp = new int[N + 2][N + 2];
    10.       for (int i = 1; i <= N; i++) {
    11.           dp[i][i] = help[i - 1] * help[i] * help[i + 1];
    12.       }
    14.       for (int L = N; L >= 1; L--) {
    15.           for (int R = L + 1; R <= N; R++) {
    16.               // 求解dp[L][R]，表示help[L..R]上打爆所有气球的最大分数
    17.               // 最后打爆help[L]的方案
    18.               int finalL = dp[L + 1][R] + help[L - 1] * help[L] * help[R + 1];
    19.               // 最后打爆help[R]的方案
    20.               int finalR = dp[L][R - 1] + help[L - 1] * help[R] * help[R + 1];
    22.               dp[L][R] = Math.max(finalL, finalR);
    23.               // 尝试中间位置的气球最后被打爆的每一种方案
    24.               for (int i = L + 1; i < R; i++) {
    25.                   dp[L][R] = Math.max(dp[L][R], help[L - 1] * help[i] * help[R + 1]
    26.                                       + dp[L][i - 1] + dp[i + 1][R]);
    27.               }
    28.           }
    29.       }
    30.       return dp[1][N];
    31. }
  • 是怎么想到要最后打爆这个思路的？
    • 假设你一开始想得是谁先打爆， 那么你要满足潜台词就没那么容易了