DP detailed explanation with commented code
Imagine we are covering the floor with carpets from left to right. At any point in this exercise, we will be at some point i and have carpetsRemaining carpets r
Imagine we are covering the floor with carpets from left to right. At any point in this exercise, we will be at some point i and have carpetsRemaining carpets remaining. At this point we are only concerned with covering the floor from i to n - 1. \nIn other words i can say that the state at any point is fully defined by (current position, carpets remaining)\n\nWhen we are standing at index i, we have 2 choices\n\t* either skip this tile and leave it uncovered\n\t* use one carpet starting from here.\n\nFirst off, If we are currently on a black tile, it makes no sense to start a new carpet here, so we just move one step to the right. (whatever white tiles we cover by starting here, we can cover from i + 1 and possibly more)\nNow that we are on a white tile, \n\t* If we apply option 1 and skip this tile, we would expose 1 white tile and continue the exercise from tile i + 1 with the same number of carpets remaining\n\t* If we apply option 2 and start a new carpet here, we would use one carpet and continue the exercise from tile i + carpetLen.\n\twe would obviously want to take the option which would expose the minumum number of white tiles. \n\nIf f( i , carpetsRemaining ) represents the minimum number if white tiles exposed for the floor from i to n - 1 with carpetsRemaining carpets remaining, \n//base cases\n* if( i >= n) then ans = 0. ( we have fully covered the floor and are standing to the right of it)\n* if( carpetsRemaining == 0 ) then ans = number of zeroes from i to n - 1. (We dont have any more carpets and will expose everything here on out)\n```\n\tif(i >= a.length) {\n\t\treturn 0;\n\t}\n\tif(carpets_left == 0) {\n\t\treturn suffix[i];      //suffix[i] = number of white tiles from index i to n (can be calculated using a simple for loop)\n\t}\n```\n//recursive cases\n* if( floor[i] == BLACK ) then ans = f ( i + 1, carpetsRemaining). (Just ignore this tile, continue from next index)\n* if( floor[i] == WHITE ) then ans = Max of\n\t\t\t\t\t\t\t\t\t* 1 + f( i + 1, carpetsRemaining)      (expose this tile, hence + 1, and continue with same number of carpets)\n\t\t\t\t\t\t\t\t\t* f( i + carpetLen, carpetsRemaining - 1 )      (start a new carpet here, skip carpetLen tiles, but have 1 less carpet)\n\n```\n\t // first check if this state has already been visited, if so return the answer already computed\n\tif(dp[i][carpets_left] != UNVISITED) {      \n\t\treturn dp[i][carpets_left];\n\t}\n\tif(a[i] == BLACK) {\n\t\t//this tile is black, skip it\n\t\tdp[i][carpets_left] = f(i + 1, carpets_left, a, dp, suffix, carpetLen);\n\t}\n\telse {\n\t\t//start carpet here\n\t\tint start_carpet_here = f(i + carpetLen, carpets_left - 1, a, dp, suffix, carpetLen);\n\t\t//dont start carpet here\n\t\tint dont_start_carpet_here = 1 + f(i + 1, carpets_left, a, dp, suffix, carpetLen);\n\t\tdp[i][carpets_left] = Math.min(start_carpet_here, dont_start_carpet_here);\n\t}\n\n\treturn dp[i][carpets_left];\n```\n\nThere are (n * numCarpets) states, we momoize the result for each state in a 2D array.\nTime Complexity: O(n * numCarpets)\nSpace Complexity: O(n * numCarpets)\n\nFull Code:\n```\nclass Solution {\n    private static final int UNVISITED = -1;\n    private static final char BLACK = \'0\';\n    private static final char WHITE = \'1\';\n\n    private int f(int i, int carpets_left, char[] a, int[][] dp, int[] suffix, int carpetLen) {\n        if(i >= a.length) {\n            return 0;\n        }\n        if(carpets_left == 0) {\n            return suffix[i];\n        }\n        if(dp[i][carpets_left] != UNVISITED) {\n            return dp[i][carpets_left];\n        }\n        if(a[i] == BLACK) {\n            dp[i][carpets_left] = f(i + 1, carpets_left, a, dp, suffix, carpetLen);\n        }\n        else {\n            //start carpet here\n            int start = f(i + carpetLen, carpets_left - 1, a, dp, suffix, carpetLen);\n            //dont start carpet here\n            int dont = 1 + f(i + 1, carpets_left, a, dp, suffix, carpetLen);\n\n            dp[i][carpets_left] = Math.min(start, dont);\n        }\n\n        return dp[i][carpets_left];\n    }\n\n    public int minimumWhiteTiles(String floor, int numCarpets, int carpetLen) {\n        \n        int n = floor.length();\n        char[] a = floor.toCharArray();\n        \n        //calculating the suffix array\n        int[] suffix = new int[n + 1];\n        for(int i = n - 1; i >= 0; i--) {\n            suffix[i] = suffix[i + 1];\n            if(a[i] == WHITE) {\n                suffix[i] ++;\n            }\n        }\n        \n        int[][] dp = new int[n + 1][numCarpets + 1];\n        for(int[] row : dp) {\n            Arrays.fill(row, UNVISITED);\n        }\n\n        return f(0, numCarpets, a, dp, suffix, carpetLen);\n    }\n}\n```\n
['Dynamic Programming']