Java - Recursive DP
Intuition\nhttps://youtu.be/lPQSy4WfMOg\n\n# Complexity\n- Time complexity:\nO(floor.length * numCarpets)\n\n- Space complexity:\nO(floor.length * numCarpets)\n
# Intuition\nhttps://youtu.be/lPQSy4WfMOg\n\n# Complexity\n- Time complexity:\nO(floor.length * numCarpets)\n\n- Space complexity:\nO(floor.length * numCarpets)\n\n# Code\n```java []\nclass Solution {\n    private int[][] dp;\n    private int n;\n\n    private int minWhiteTiles(int pos, int carpetsLeft, String floor, int carpetLen) {\n        if(pos >= floor.length())\n            return 0;\n        if(dp[pos][carpetsLeft] != -1)\n            return dp[pos][carpetsLeft];\n        \n        int ans = (floor.charAt(pos) == \'1\' ? 1 : 0) + minWhiteTiles(pos + 1, carpetsLeft, floor, carpetLen);\n        if(carpetsLeft > 0)\n            ans = Math.min(ans, minWhiteTiles(pos + carpetLen, carpetsLeft - 1, floor, carpetLen));\n        \n        return dp[pos][carpetsLeft] = ans;\n    }\n    \n    public int minimumWhiteTiles(String floor, int numCarpets, int carpetLen) {\n        n = floor.length();\n        dp = new int[n + 1][numCarpets + 1];\n        for (int i = 0; i <= n; i++)\n            for(int j=0; j <= numCarpets; j++)\n                dp[i][j] = -1;\n        \n        return minWhiteTiles(0, numCarpets, floor, carpetLen);\n    }\n}\n```
['Dynamic Programming', 'Recursion', 'Java']