Java Simple Top Down DP with explanation
Basically we consider each suffix from floor[0...I] using J carpets. There are 2 transition options to consider and minimize over for this building upon "smalle
Basically we consider each suffix from ```floor[0...I]``` using ```J``` carpets. There are 2 transition options to consider and minimize over for this building upon "smaller"* subproblems.\n\nCase 1: We use a carpet that ends at ```I```th position. So this means we simply need ```subproblem(I-carpetLen, J-1)``` because all tiles from ```I-carpetLen + 1``` to ```I``` now have 0 white tiles due to spending 1 carpet so we are at pos ```I - carpetLen``` with 1 less carpet.\n\nCase 2: We do not use a carpet that ends at ```I```th position. So the ```I```th tile is uncovered. So this tile has to be included towards count of white tiles so add ```floor(I) == 0? 1 : 0```. And then we\'re left with ```subproblem(I-1, J)``` as we haven\'t spent any carpets.\n\nThat is ```subproblem(I, J) = Min(subproblem(I-carpetLen, J-1), subproblem(I-1, J) + floor(I) == 0? 1 : 0)```\n\n\\* "smaller" in sense that subproblem(I\', J\') < subproblem(I, J) if I\' <= I and J\' <= J and not case that (I\', J\') = (I, J)\n\nThere are a few edge cases that should be easily understandable from code below.\nCode:\n```\nclass Solution {\n    public int minimumWhiteTiles(String floor, int numCarpets, int carpetLen) {\n        // memo[I][J] = subproblem of floor[0...I] with J numCarpets.\n        // so I range from 0...(floor.len - 1) so floor.len possibilities\n        // and J range from 0 ... numCarpets so numCarpets+1 possibilities\n        Integer[][] memo = new Integer[floor.length()][numCarpets + 1];\n        return dfs(floor.length() - 1, numCarpets, carpetLen, memo, floor);\n    }\n    \n    // precond. i and j both >=0. don\'t add check at start, instead maintain this\n    private int dfs(int i, int j, int carpetLen, Integer[][] memo, String floor) {\n        //if (i < 0 || j < 0) {\n            //return 0;\n        //}\n        if (memo[i][j] != null) {\n            return memo[i][j];\n        }\n        int min = Integer.MAX_VALUE;\n        // case 1: only when have at least 1 carpet to work with so let one extend and end at I\n        if (j > 0) {\n            if (i - carpetLen >= 0) {\n                min = Math.min(min, dfs(i - carpetLen, j-1, carpetLen, memo, floor));\n            } else {\n                // have enough carpet to span all of [0...i] so no while tiles visible\n                memo[i][j] = 0;\n                return 0;\n            }\n        }\n        // case 2: tile does not extend till here\n        if (i > 0) {\n            min = Math.min(min, dfs(i-1, j, carpetLen, memo, floor) + ((floor.charAt(i) == \'1\')? 1 : 0));\n        } else {\n            min = Math.min(min, ((floor.charAt(i) == \'1\')? 1 : 0));\n        }\n        memo[i][j] = min;\n        return min;\n    }\n}\n```\n
['Dynamic Programming', 'Java']