Java Solution | Top-Down DP | 2 approaches
Explanation :\n\nHere, I want to showcase 2 approaches for solving the problem using memoization :\n\t\t1. counting the minimum number of exposed white tiles us
**Explanation :**\n\nHere, I want to showcase 2 approaches for solving the problem using memoization :\n\t\t1. counting the minimum number of exposed white tiles using `suffix-sum` and\n\t\t2. counting the maximum number of white tiles covered by the given carpets and subtracting this from the total number of white tiles to get the exposed white tiles using `prefix-sum`\n\n**Approach 1 :**\n\n```\npublic int minimumWhiteTiles(String floor, int numCarpets, int carpetLen) {\n        Integer[][] dp = new Integer[floor.length() + 1][numCarpets + 1];\n        int[] suffixSum = new int[floor.length()];\n        suffixSum[floor.length() - 1] = (floor.charAt(floor.length() - 1) == \'1\' ? 1 : 0);\n\n        for (int i = floor.length() - 2; i >= 0; i--) {\n            suffixSum[i] = suffixSum[i + 1] + (floor.charAt(i) == \'1\' ? 1 : 0);\n        }\n\n        return coverTilesDP(floor, 0, carpetLen, numCarpets, dp, suffixSum);\n    }\n\n    private int coverTilesDP(String str, int idx, int carpetLen,\n                             int numCarpets, Integer[][] dp, int[] suffixSum) {\n        if (idx >= str.length()) {\n            return 0;\n        } else if (numCarpets == 0) {\n            return suffixSum[idx];\n        }\n\n        if (dp[idx][numCarpets] != null) {\n            return dp[idx][numCarpets];\n        }\n\t\t\n        // include\n        int min1 = coverTilesDP(str, idx + carpetLen, carpetLen, numCarpets - 1, dp, suffixSum);\n        // exclude\n        int min2 = coverTilesDP(str, idx + 1, carpetLen, numCarpets, dp, suffixSum) + (str.charAt(idx) == \'1\' ? 1 : 0);\n\n        return dp[idx][numCarpets] = Math.min(min1, min2);\n    }\n```\n\n**Approach 2 :**\n\n```\n    public int minimumWhiteTiles(String floor, int numCarpets, int carpetLen) {\n        Integer[][] dp = new Integer[floor.length() + 1][numCarpets + 1];\n        int[] prefixSum = new int[floor.length()];\n        prefixSum[0] = (floor.charAt(0) == \'1\' ? 1 : 0);\n\n        for (int i = 1; i < floor.length(); i++) {\n            prefixSum[i] = prefixSum[i - 1] + (floor.charAt(i) == \'1\' ? 1 : 0);\n        }\n        return prefixSum[floor.length() - 1] - coverTilesDP(floor, 0, carpetLen,\n                                                            numCarpets, dp, prefixSum);\n    }\n\n    private int coverTilesDP(String str, int idx, int carpetLen,\n                             int numCarpets, Integer[][] dp, int[] prefixSum) {\n        if (idx >= str.length() || numCarpets == 0) {\n            return 0;\n        }\n\n        if (dp[idx][numCarpets] != null) {\n            return dp[idx][numCarpets];\n        }\n\n        // include\n        int max1 = coverTilesDP(str, idx + carpetLen, carpetLen, numCarpets - 1, dp, prefixSum) +\n                   (prefixSum[Math.min(idx + carpetLen - 1, prefixSum.length - 1)] - (idx >= 1 ? prefixSum[idx - 1] : 0));\n        // exclude\n        int max2 = coverTilesDP(str, idx + 1, carpetLen, numCarpets, dp, prefixSum);\n\n        return dp[idx][numCarpets] = Math.max(max1, max2);\n    }\n```\n\n**PS -** Any suggestions or improvements are most welcome.
['Dynamic Programming', 'Memoization', 'Prefix Sum', 'Java']