Where is wrong(C++)?


  • 0
    W
    class Solution {
    public:
    	int removeBoxes(vector<int>& boxes) {
    		if (boxes.empty()) return 0;
    		boxes.push_back(-1);
    		// preprocessing
    		// [1,1,1,3,3,2,3,3,3,1,1] would become
    		// color : [1,3,2,3,1]
    		// length :   [3,2,1,3,2]
    		vector<int> color;
    		vector<int> length;
    		int currColor, currLen;
    		for (int i = 0; i < boxes.size(); i++) {
    			if (i == 0 || boxes[i] != boxes[i - 1]) {
    				if (i > 0 && boxes[i] != boxes[i - 1]) {
    					color.push_back(currColor);
    					length.push_back(currLen);
    				}
    				currColor = boxes[i];
    				currLen = 1;
    			} else {
    				currLen++;
    			}
    		}
    		vector<vector<int>> dp(color.size(), vector<int>(color.size()));
    		for (int offset = 0; offset < color.size(); offset++) {
    			for (int i = 0; i < color.size() - offset; i++) {
    				if (offset == 0) dp[i][i + offset] = length[i] * length[i];
    				else if (offset == 1) dp[i][i + offset] = dp[i][i] + dp[i + offset][i + offset];
    				else {
    					if (color[i] == color[i + offset]) {
    						// merge color i
    						dp[i][i + offset] = 0;
    						int count = length[i], prev = i;
    						for (int t = i + 1; t <= i + offset; t++) {
    							if (color[t] == color[i]) {
    								count += length[t];
    								dp[i][i + offset] += dp[prev + 1][t - 1];
    								prev = t;
    							}
    						}
    						dp[i][i + offset] += count * count;
    					} else {
    						dp[i][i + offset] = INT_MIN;
    					}
    					// dp[i][j] = max(dp[i][j], dp[i][t] + dp[t + 1][j]) where t from i to j - 1
    					for (int t = i; t < i + offset; t++) {
    						dp[i][i + offset] = max(dp[i][i + offset], dp[i][t] + dp[t + 1][i + offset]);
    					}
    				}
    			}
    		}
    		return dp[0].back();
    	}
    };
    

  • 0
    W

    I know where I am wrong.

    class Solution {
    public:
    	int removeBoxes(vector<int>& boxes) {
    		if (boxes.empty()) return 0;
    		boxes.push_back(-1);
    		// preprocessing
    		// [1,1,1,3,3,2,3,3,3,1,1] would become
    		// color : [1,3,2,3,1]
    		// length :   [3,2,1,3,2]
    		vector<int> color;
    		vector<int> length;
    		int currColor, currLen;
    		for (int i = 0; i < boxes.size(); i++) {
    			if (i == 0 || boxes[i] != boxes[i - 1]) {
    				if (i > 0 && boxes[i] != boxes[i - 1]) {
    					color.push_back(currColor);
    					length.push_back(currLen);
    				}
    				currColor = boxes[i];
    				currLen = 1;
    			} else {
    				currLen++;
    			}
    		}
    		vector<vector<int>> dp(color.size(), vector<int>(color.size()));
    		for (int offset = 0; offset < color.size(); offset++) {
    			for (int i = 0; i < color.size() - offset; i++) {
    				if (offset == 0) dp[i][i + offset] = length[i] * length[i];
    				else if (offset == 1) dp[i][i + offset] = dp[i][i] + dp[i + offset][i + offset];
    				else {
    					dp[i][i + offset] = INT_MIN;
    					if (color[i] == color[i + offset]) {
    						// !!! middle boxes with the same color maybe not participate in merging
    						dfs(dp, color, length, i + offset, i, i + 1, length[i] + length[i + offset], 0, dp[i][i + offset]);
    					}
    					// dp[i][j] = max(dp[i][j], dp[i][t] + dp[t + 1][j]) where t from i to j - 1
    					for (int t = i; t < i + offset; t++) {
    						dp[i][i + offset] = max(dp[i][i + offset], dp[i][t] + dp[t + 1][i + offset]);
    					}
    				}
    			}
    		}
    		return dp[0].back();
    	}
    	void dfs(vector<vector<int>>& dp, vector<int>& color, vector<int>& length, int end, int prev, int curr, int count, int sum, int& res) {
    		if (curr == end) {
    			res = max(res, sum + dp[prev + 1][end - 1] + count * count);
    		} else {
    			if (color[curr] == color[end]) {
    				dfs(dp, color, length, end, curr, curr + 1, count + length[curr], sum + dp[prev + 1][curr - 1], res);
    			}
    			dfs(dp, color, length, end, prev, curr + 1, count, sum, res);
    		}
    	}
    };
    

Log in to reply
 

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