解法一：记忆化搜索

参考官方题解：https://leetcode-cn.com/problems/remove-boxes/solution/yi-chu-he-zi-by-leetcode-solution/
太顶了😱

  1. class Solution {
  2.     public int removeBoxes(int[] boxes) {
  3.         final int n = boxes.length;
  4.         int[][][] dp = new int[n][n][n];
  5.         return f(dp, boxes, 0, boxes.length - 1, 0);
  6.     }
  8.     private int f(int[][][] dp, final int[] boxes, int l, int r, int k) {
  9.         if (l > r) {
  10.             return 0;
  11.         }
  12.         if (dp[l][r][k] != 0) {
  13.             return dp[l][r][k];
  14.         }
  15.         for (; (r > l) && (boxes[r] == boxes[r - 1]); --r, ++k) ;
  16.         dp[l][r][k] = f(dp, boxes, l, r - 1, 0) + (k + 1) * (k + 1);
  17.         for (int i = l; i < r; ++i) {
  18.             if (boxes[i] == boxes[r]) {
  19.                 dp[l][r][k] = Math.max(dp[l][r][k], f(dp, boxes, l, i, k + 1) + f(dp, boxes, i + 1, r - 1, 0));
  20.             }
  21.         }
  22.         return dp[l][r][k];
  23.     }
  24. }