Java | Dynamic Programming | Prefix Sum | Comments Explanation
\nclass Solution {\n    public Integer dp[][];\n    public int minimumWhiteTiles(String floor, int numCarpets, int carpetLen) {\n        int n = floor.length();
```\nclass Solution {\n    public Integer dp[][];\n    public int minimumWhiteTiles(String floor, int numCarpets, int carpetLen) {\n        int n = floor.length();\n        // if floor length is less than or equal to avaliable tiles return 0\n        if(n <= numCarpets*carpetLen) return 0;\n        \n        //dp array\n        dp = new Integer[n+1][numCarpets+1];\n        \n        //Prefix sum array for floor string\n        int[] whiteTiles = new int[n+1];\n        for(int i=1;i<=n;i++) {\n            int curVal = floor.charAt(i-1)==\'1\' ? 1 : 0;\n            whiteTiles[i] = whiteTiles[i-1] + curVal;\n        }\n        \n        //finding maximum tiles we can cover with available numCarpets * carpetLen tiles\n        int maxTilesCovered = maxTilesCanCover(whiteTiles, 1, numCarpets, carpetLen, n+1);\n        \n        // Subtracting all tiles which need to covered minus maximum no of tiles we were able to cover\n        return whiteTiles[n] - maxTilesCovered;\n    }\n    public int maxTilesCanCover(int[] tiles , int ind, int numCarpets, int len, int n) {\n        //base condition\n        if(ind>=n || numCarpets<=0) return 0;\n        \n        //dp state to cache precomputed state\n        if(dp[ind][numCarpets]!=null) return dp[ind][numCarpets];\n        int ans = maxTilesCanCover(tiles, ind+1, numCarpets, len, n);\n        \n        //if the tile length is greater than array length taking the minimum of them\n        int lastInd = Math.min(ind+len-1, n-1);\n        \n        // finding no of tiles present in the given tile length\n        int curTileLen = tiles[lastInd]-tiles[ind-1];\n        \n        //Only computing when the current Tile length is less than or equal to available numCarpets * carpetLen tiles\n        if(curTileLen<=(numCarpets*len)) {\n            int noOfTilesReq = (int) Math.ceil((double) curTileLen/len);\n            ans = Math.max(ans,curTileLen + maxTilesCanCover(tiles, lastInd+1, numCarpets-noOfTilesReq, len,n));\n        }\n        \n        //Storing and returning the computed result\n        return dp[ind][numCarpets]=ans;\n    }\n}\n```
['Dynamic Programming', 'Memoization', 'Prefix Sum', 'Java']