C++ DP house robber
This problem can be converted to house robber then solved by dynamic programming.\nWhen the total length of carpet is equal to or exceed the length of the floor
This problem can be converted to [house robber](https://leetcode.com/problems/house-robber/) then solved by dynamic programming.\nWhen the total length of carpet is equal to or exceed the length of the floor, there should be no white left. When it\'s not, we should always looking for non-overlapping solution as at least one of the optimal solution doesn\'t include overlapping. The reason is that we can always rearrange carpets to not overlap and covering all the original tiles and some more.\nSo we can calculate how many white tiles can be covered starting from each position, the problem is to select ```numCarpet``` of positions, with minimum distance of any two position is ```carpetLen```, to get the maximum sum. It\'s equivalent to house robber except that we not only can\'t rob consecutive houses, we can\'t rob houses within some given distance ```carpetLen```. Also we have a fixed amount of house we have to rob, so instead of a 1D DP as we did in house robber, a standard 2D DP approach should suffice. See annotation for details.\n```\nclass Solution {\npublic:\n    int minimumWhiteTiles(string floor, int numCarpets, int carpetLen) {\n\t\t//too many carpets, cover all the floor\n        int l = floor.size();\n        if(numCarpets*carpetLen>=l) {return 0;}\n\t\t\n        // sliding window to calculate how many white tiles can be covered for a carpet starting at position i\n        int white = 0;             // number of total white tiles on the floor\n        int m = l-carpetLen+1;     // number of possible carpet starting position\n        vector<int> cover(m,0);    // number of white tiles covered for a carpet starting at each position\n        for(int i=0; i<carpetLen; i++){\n            cover[0] += (floor[i]==\'1\');\n            white += (floor[i]==\'1\');\n        }\n        for(int i=1; i<m; i++){\n            cover[i] = cover[i-1] - (floor[i-1]==\'1\') + (floor[i+carpetLen-1]==\'1\');\n            white += (floor[i+carpetLen-1]==\'1\');\n        }\n\t\t\n        // dp to find the maximum sum of numCarpets elements from cover[0:m-1], \n\t\t// with any of the two elements having minimum distance of carpetLen\n\t\t// dp[k][i] stands for the maximum sum for k elements in cover[0:i]\n        vector<vector<int>> dp(numCarpets+1, vector<int>(m,0));\n        dp[1][0] = cover[0];\n        for(int i=1; i<m; i++){\n            dp[1][i] = max(dp[1][i-1],cover[i]);\n        }\n        for(int carpet=2; carpet<=numCarpets; carpet++){\n            for(int i=(carpet-1)*carpetLen; i<m; i++){\n\t\t\t\t// either we don\'t select current element, \n\t\t\t\t// or we select current element and limit the range of last selected element before i-carpetLen\n                dp[carpet][i] = max(dp[carpet][i-1],cover[i]+dp[carpet-1][i-carpetLen]);\n            }\n        }\n        return white-dp[numCarpets][m-1];\n    }\n};\n```\nThis solution should be able to optimized to O(N) space complexity by using two 1D vectors.
['Dynamic Programming', 'C']