package com.fishercoder.solutions;

/**
 * 546. Remove Boxes
 *
 * Given several boxes with different colors represented by different positive numbers.
 * You may experience several rounds to remove boxes until there is no box left.
 * Each time you can choose some continuous boxes with the same color (composed of k boxes, k >= 1), remove them and get k*k points.
 * Find the maximum points you can get.

 Example 1:
 Input:

 [1, 3, 2, 2, 2, 3, 4, 3, 1]
 Output:
 23

 Explanation:
 [1, 3, 2, 2, 2, 3, 4, 3, 1]
 ----> [1, 3, 3, 4, 3, 1] (3*3=9 points)
 ----> [1, 3, 3, 3, 1] (1*1=1 points)
 ----> [1, 1] (3*3=9 points)
 ----> [] (2*2=4 points)
 Note: The number of boxes n would not exceed 100.

 */

public class _546 {
    /**
     * credit: https://leetcode.com/articles/remove-boxes/#approach-2-using-dp-with-memorizationaccepted
     *
     * For an entry in dp[l][r][k], l represents the starting index of the subarray,
     * r represents the ending index of the subarray
     * and k represents the number of elements similar to the r​th element
     * following it which can be combined to obtain the point information to be stored in dp[l][r][k].
     */
    public int removeBoxes(int[] boxes) {
        int[][][] dp = new int[100][100][100];
        return calculatePoints(boxes, dp, 0, boxes.length - 1, 0);
    }

    public int calculatePoints(int[] boxes, int[][][] dp, int l, int r, int k) {
        if (l > r) {
            return 0;
        }
        if (dp[l][r][k] != 0) {
            return dp[l][r][k];
        }
        while (r > l && boxes[r] == boxes[r - 1]) {
            r--;
            k++;
        }
        dp[l][r][k] = calculatePoints(boxes, dp, l, r - 1, 0) + (k + 1) * (k + 1);
        for (int i = l; i < r; i++) {
            if (boxes[i] == boxes[r]) {
                dp[l][r][k] = Math.max(dp[l][r][k],
                        calculatePoints(boxes, dp, l, i, k + 1) + calculatePoints(boxes, dp, i + 1, r - 1, 0));
            }
        }
        return dp[l][r][k];
    }
}

@@ -717,16 +717,56 @@
  _546 %7B%0A
+    public static class Solution1 %7B%0A    
     /**%0A
@@ -770,16 +770,20 @@
 **%0A     
+   
+ 
 * credit
@@ -879,18 +879,26 @@
 ed%0A     
-*%0A
+    *%0A    
      * F
@@ -979,16 +979,20 @@
 y,%0A     
+  
+  
 * r repr
@@ -1031,16 +1031,20 @@
 ubarray%0A
+    
      * a
@@ -1110,16 +1110,20 @@
 element%0A
+    
      * f
@@ -1222,19 +1222,27 @@
 %5D.%0A     
-*/%0A
+    */%0A    
     publ
@@ -1283,16 +1283,20 @@
         
+   
+ 
 int%5B%5D%5B%5D%5B
@@ -1326,16 +1326,20 @@
 %5D%5B100%5D;%0A
+    
         
@@ -1397,16 +1397,20 @@
  1, 0);%0A
+    
     %7D%0A%0A 
@@ -1408,24 +1408,28 @@
      %7D%0A%0A    
+ 
+   
 public int c
@@ -1497,24 +1497,28 @@
 ) %7B%0A        
+    
 if (l %3E r) %7B
@@ -1514,24 +1514,28 @@
 f (l %3E r) %7B%0A
+    
             
@@ -1544,34 +1544,42 @@
 turn 0;%0A        
-%7D%0A
+    %7D%0A    
         if (dp%5Bl
@@ -1598,32 +1598,36 @@
 ) %7B%0A            
+   
+ 
 return dp%5Bl%5D%5Br%5D%5B
@@ -1630,34 +1630,42 @@
 %5Br%5D%5Bk%5D;%0A        
-%7D%0A
+    %7D%0A    
         while (r
@@ -1716,13 +1716,21 @@
     
+  
+  
 r--;%0A
+    
     
@@ -1742,16 +1742,20 @@
    k++;%0A
+    
         
@@ -1756,32 +1756,36 @@
       %7D%0A        
+    
 dp%5Bl%5D%5Br%5D%5Bk%5D = ca
@@ -1851,16 +1851,20 @@
         
+    
 for (int
@@ -1893,24 +1893,28 @@
             
+   
+ 
 if (boxes%5Bi%5D
@@ -1925,24 +1925,28 @@
 boxes%5Br%5D) %7B%0A
+    
             
@@ -1985,16 +1985,20 @@
 %5Br%5D%5Bk%5D,%0A
+    
         
@@ -2113,26 +2113,33 @@
         
+ 
-%7D%0A
+   %7D%0A   
         
 %7D%0A      
@@ -2122,34 +2122,39 @@
    %7D%0A           
+ 
 %7D%0A
+    
         return d
@@ -2161,20 +2161,30 @@
 p%5Bl%5D%5Br%5D%5Bk%5D;%0A
+        %7D%0A
     %7D%0A%7D%0A

refactor 546