DP
Intuition\n Describe your first thoughts on how to solve this problem. \nCover the tiles carpet by carpet from end to beginning. for each carpet, choose the the
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nCover the tiles carpet by carpet from end to beginning. for each carpet, choose the the place that the sum of the tiles he and his predecessors cover the most.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity:O(N*K)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:O(N*K)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public int minimumWhiteTiles(String floor, int numCarpets, int carpetLen) {\n        char []arr=floor.toCharArray();\n        int[][] mat=new int[numCarpets][arr.length];\n        int max=0;\n        int[]sums=new int[arr.length];\n        for(int i=0;i<numCarpets;i++)\n        {\n            int sum=0;\n            for(int j=arr.length-1;j>-1;j--)\n            {\n                if(arr[j]==\'1\')\n                    sum++;\n                if(j+carpetLen<arr.length){\n                    if(arr[j+carpetLen]==\'1\')\n                        sum--;      \n                    mat[i][j]=sum+sums[j+carpetLen];\n                }\n                else\n                    mat[i][j]=sum;\n            }\n            sums[arr.length-1]=mat[i][arr.length-1];\n             for(int j=arr.length-2;j>-1;j--)\n             {\n                 sums[j]=Math.max(mat[i][j],sums[j+1]);\n             }\n             \n        }\n        int sum=0;\n        for(char ch:arr)\n           if(ch==\'1\')\n                sum++;\n        return sum-sums[0]; \n    }\n}\n```
['Java']