Java DP + Memorization 60ms


  • 15
    W

    When facing this problem, I am keeping thinking how to simulate the case when boxes[i] == boxes[j] when i and j are not consecutive. It turns out that the dp matrix needs one more dimension to store such state. So we are going to define the state as

    dp[i][j][k] represents the max points from box[i] to box[j] with k boxes whose values equal to box[i]
    

    The transformation function is as below

    dp[i][j][k] = max(dp[i+1][m-1][1] + dp[m][j][k+1]) when box[i] = box[m]
    

    So the Java code with memorization is as below. Kindly ask me any questions.

      public int removeBoxes(int[] boxes) {
            if (boxes == null || boxes.length == 0) {
                return 0;
            }
    
            int size = boxes.length;
            int[][][] dp = new int[size][size][size];
    
            return get(dp, boxes, 0, size-1, 1);
        }
    
        private int get(int[][][] dp, int[] boxes, int i, int j, int k) {
            if (i > j) {
                return 0;
            } else if (i == j) {
                return k * k;
            } else if (dp[i][j][k] != 0) {
                return dp[i][j][k];
            } else {
                int temp = get(dp, boxes, i + 1, j, 1) + k * k;
    
                for (int m = i + 1; m <= j; m++) {
                    if (boxes[i] == boxes[m]) {
                        temp = Math.max(temp, get(dp, boxes, i + 1, m - 1, 1) + get(dp, boxes, m, j, k + 1));
                    }
                }
    
                dp[i][j][k] = temp;
                return temp;
            }
    
    
        }
    

  • 0

    @wihoho2

    Well, finally one non TLE solution. I considered to use DP and noticed 3 dimension is needed. But it is really rare to see that lol. Good DP solution!


  • 0
    Z

    Hi, I am not very sure why dp[0][size - 1][1] should be the final answer? Why k = 1 here? I thought we would take max score out of all the k in dp[0][size - 1][k]


  • 0
    Z

  • 1
    S

    Thanks for your solution

    From your explanation

    dp[i][j][k] represents the max points from box[i] to box[j] with k boxes whose values equal to box[i]

    However, I think dp[i][j][k] should mean the max points from box[i] to box[j] with k boxes of value box[i] merged.

    And also the DP

    We have two condition

    1. We choose to merge k boxes

    this mean we would have score = dp(i+1, j, 1) + k * k ...............(1)

    1. We don't merge k boxes
      so, we can continue to find box which is the same
      this means when we find box m equal to box i, we can have one more box, so k become k + 1
      So we have dp(i+1, m-1, 1) + dp (m, j, k + 1) ...............(2)
      the first term is the other boxes
      and the second term contain information of the same boxes(box[i] or box[m]) we have found till now

    dp[i][j][k] = max ((1), (2))


  • 0
    C

    Nice solution, I was finding hard to simulate this in code.

    what is the time complexity of this? is it n!?


  • 1
    M

    Thanks for sharing.
    But 3-dimensional DP....
    could anyone kindly tell me which company asks this Q? Is this an interview question for new grads?


  • 0
    A
    This post is deleted!

  • 0
    C
    This post is deleted!

  • 0
    F
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.