Java | DP | Memoization
Do Binary Search and store indices of whites tiles.\n2. We can use DP here now where:\ndp(floorLength, numCarpets) = max(dp(floorLength - carpetLen, numCarpets 
1. Do Binary Search and store indices of whites tiles.\n2. We can use DP here now where:\ndp(floorLength, numCarpets) = max(dp(floorLength - carpetLen, numCarpets - 1) + numOfWhiteTilesInRange(floorLength - carpetLen, floorLength), dp(floorLength - carpetLen, numCarpets - 1)) -> number of white tiles covered from index 0 to floorLength using numCarpets number of carpets.\n3. Base Conditions:\nif (floorLength < 0 || numCarpets <= 0) return 0;\n4. ans = whiteTiles.size() - dp(floorLength, numCarpets)\n```\nclass Solution {\n    public int minimumWhiteTiles(String floor, int numCarpets, int carpetLen) {\n        int floorLength = floor.length();\n        List<Integer> whiteTiles = new ArrayList<>();\n        for (int tile = 0; tile < floorLength; tile += 1) {\n            if (floor.charAt(tile) == \'1\') {\n                whiteTiles.add(tile);\n            }\n        }\n        Integer[][] dp = new Integer[floorLength][numCarpets + 1];\n        System.out.println(minimumWhiteTiles(floorLength - 1, numCarpets, carpetLen, dp, whiteTiles) + "-" + whiteTiles.size());\n        return whiteTiles.size() - minimumWhiteTiles(floorLength - 1, numCarpets, carpetLen, dp, whiteTiles);\n    }\n    \n    private int minimumWhiteTiles(int floorLength, int numCarpets, int carpetLen, Integer[][] dp, List<Integer> whiteTiles) {\n        if (floorLength < 0 || numCarpets <= 0) {\n            return 0;\n        }\n        if (dp[floorLength][numCarpets] != null) {\n            return dp[floorLength][numCarpets];\n        }\n        return dp[floorLength][numCarpets] = Math.max(minimumWhiteTiles(floorLength - carpetLen, numCarpets - 1, carpetLen, dp, whiteTiles) + numOfWhiteTilesInRange(floorLength - carpetLen, floorLength, whiteTiles), minimumWhiteTiles(floorLength - 1, numCarpets, carpetLen, dp, whiteTiles));\n    }\n    \n    private int numOfWhiteTilesInRange(int start, int end, List<Integer> whiteTiles) {\n        int maxIndex = ceil(end, whiteTiles);\n        int minIndex = ceil(start, whiteTiles);\n        return maxIndex - minIndex;\n    }\n    \n    int ceil(int idx, List<Integer> whiteTiles) {\n        int ans = -1;\n        int start = 0;\n        int end = whiteTiles.size() - 1;\n        while(start <= end) {\n            int mid = start + (end - start) / 2;\n            if(whiteTiles.get(mid) <= idx) {\n                ans = mid;\n                start = mid + 1;\n            } else {\n                end = mid - 1;\n            }\n        }\n        return ans + 1;\n    }\n}\n```
['Dynamic Programming', 'Memoization', 'Java']