Interview Preparation
Let me clarify the question once ...\ntestcase\nconstraints :\n1 <= carpetLen <= floor.length <= 1000\nfloor[i] is either \'0\' or \'1\'.\n1 <= numCarpets <= 10
Let me clarify the question once ...\ntestcase\nconstraints :\n1 <= carpetLen <= floor.length <= 1000\nfloor[i] is either \'0\' or \'1\'.\n1 <= numCarpets <= 1000\nGive me a few minutes to think it through\ncomment - BF, optimal\ncode\n\n\n# Intuition\ndp\n\n# Approach - tabulation\n\n# Complexity\n- Time complexity:\n$$O(n*numCarpets)$$\n\n- Space complexity:\n$$O(n*numsCarpets)$$\n\n# Code\n```\nclass Solution {\npublic:\n    int minimumWhiteTiles(string floor, int numCarpets, int carpetLen) {\n        int n = floor.size();\n        vector<vector<int>> dp(1001, vector<int>(1001, 0));\n        for(int i=n-1; i>=0; i--) {\n            dp[i][0] = dp[i+1][0] + (floor[i] == \'1\');\n            for(int j=1; j<=numCarpets; j++) {\n                dp[i][j] = min(dp[i+1][j] + (floor[i] == \'1\'), dp[min(1000, i+carpetLen)][j-1]);\n            }\n        }\n        return dp[0][numCarpets];\n    }\n};\n```\n\n# Approach - memoization\n\n# Complexity\n- Time complexity:\n$$O(n*numCarpets)$$\n\n- Space complexity:\n$$O(n*numsCarpets)$$\n\n# Code\n```\nclass Solution {\npublic:\n    int recursion(string &floor, int numCar, int carLen, int pos, int used, vector<int> &suffix, vector<vector<int>> &dp) {\n        if(pos >= floor.size()) {\n            return 0;\n        }\n        if(used == numCar) {\n            return suffix[pos];\n        }\n        if(dp[pos][used] != -1) {\n            return dp[pos][used];\n        }\n        return dp[pos][used] = min(recursion(floor, numCar, carLen, pos+1, used, suffix, dp)+(floor[pos]==\'1\'), recursion(floor, numCar, carLen, pos+carLen, used+1, suffix, dp));\n    }\n    int minimumWhiteTiles(string floor, int numCarpets, int carpetLen) {\n        int n = floor.size();\n        vector<vector<int>> dp(1001, vector<int>(1001, -1));\n        vector<int> suffix(n);\n        suffix[n-1] = floor[n-1]==\'1\';\n        for(int i=n-2; i>=0; i--) {\n            suffix[i] = suffix[i+1]+(floor[i]==\'1\');\n        }\n        return recursion(floor, numCarpets, carpetLen, 0, 0, suffix, dp);\n    }\n};\n```\n
['C++']