Passed 51/60 test cases, straight forward DP using 2D Array, anyone know why am I wrong?


  • 0
    G
    public class Solution {
        public int removeBoxes(int[] boxes) {
            int len = boxes.length;
            int[][] dp = new int[len][len];
            for(int i =0; i< len; i++)  dp[i][i] =1;
            for(int l = 1; l< len; l++){
                for(int i = 0; i< len-l; i++){
                    int j = i+l;
                    if(boxes[i] == boxes[j])
                        dp[i][j] = narrow(boxes, dp, i, j);
                    else
                        dp[i][j] = split(boxes, dp, i, j);
                }
            }
            return dp[0][len-1];
        }
        public int split(int[] boxes, int[][] dp, int start, int end){
            int res = 0;
            if(start + 1 == end)
                return 2;
            for(int i = start; i<end; i++)
                res = Math.max(res, dp[start][i]+dp[i+1][end]);
            return res;
        }
        public int narrow(int[] boxes, int[][] dp, int start, int end){
            int cnt = 2, s = start+1, res = 0;
            int bench = boxes[start];
            for(int i = start+1; i<end; i++){
                if(boxes[i] == bench){
                    cnt++;
                    if(s != i)
                        res += dp[s][i-1];
                    s = i+1;
                }
            }
            if(s<end)
                res+=dp[s][end-1];
            return cnt*cnt+res;
        }
    

    }


Log in to reply
 

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