JAVA Simple Solution with Explaination
I was having the problem to think but got intuition of DP by seeing constraints. But Now how to implement DP what will be the variables to play . Basically thin
I was having the problem to think but got intuition of DP by seeing constraints. But Now how to implement DP what will be the variables to play . Basically think on which variables you are dependent;\nYes You have to travel the complete the floor string so this variable is changing and second the number of carpet is changing. \ncarpet length is constant .\nThis is similar to knapsack yes , here each carpet has value that is length. \nAt each index you have two choice either use carpet or don\'t use it;\nif already black skip and move forward\nif white you can use carpet or you can leave white (thus cnt will be increased)\n\nif all carpet are used and still floor is not completed just return number of white tiles are left;\nbelow is the code\n\n\nclass Solution {\n    public int minimumWhiteTiles(String floor, int numCarpets, int carpetLen) {\n        // we have to cover the tiles  we first see the color if it is black \n        // we leave if its white we have option to jump or we cover it;\n        int dp[][]= new int[floor.length()+1][numCarpets+1];\n        for(int a[]: dp){\n            Arrays.fill(a, -1);\n        }\n        return helper( 0, numCarpets, carpetLen, dp, floor);\n    }\n    public int helper(int i, int nc, int l, int[][] dp, String s){\n        \n        if(i>= s.length()) return 0;\n        if(nc<=0){\n            int cnt=0;\n            for(int j= i; j<s.length(); j++){\n                if(s.charAt(j)==\'1\'){\n                    cnt++;\n                }\n            }\n            return cnt;\n        }\n        \n        if(dp[i][nc]!=-1) return dp[i][nc];\n        \n        \n        if(s.charAt(i)==\'0\'){\n            return dp[i][nc]= helper(i+1, nc,l , dp , s);\n        }\n        else{\n            int jump= 1+ helper(i+1, nc, l, dp, s);\n            int cover= helper(i+ l, nc-1, l, dp, s);\n            \n            return dp[i][nc]= Math.min(jump, cover);\n        }\n        \n    }\n}
['Dynamic Programming', 'Java']