DP | Memorization | Easy to Understand solution | C++ | O(n^2) time and O(n^2) space |
We can solve this problem by using standard concepts of solving a 2-d DP problem.\nFor each tile, we have two options --\ni) We place a the carpet starting from
We can solve this problem by using standard concepts of solving a 2-d DP problem.\nFor each tile, we have two options --\ni) We place a the carpet starting from the current tile\nii) We do not place a carpet\n\nFurther, here is an observations to be made\n-- Placing carpet starting from a black tile is not feasible. SO before placing a carpet, we will check whether the current tile is white or not.\n\n\nBelow is the code for the approach explained above. Lines have been commented in order to understand better.\n\n```\nint solve(string &a,int i,int j,int k,int len,vector<vector<long long int>> &dp)\n{\n    \n    // dp states --\n    //     i --> represents the index of the tiles\n    //     j --> represents the number of black carpets used\n    \n    if(i>=a.size())\n    {\n        // base case\n        return 0;\n    }\n    \n    if(dp[i][j]!=-1)\n    {\n        // since the current tile is already black, no need of covering it\n        \n        return dp[i][j];\n    }\n    \n    \n    if(a[i]==\'1\')\n    {\n        // the current tile is white in color, so we have two options\n        \n        int op1=INT_MAX,op2=INT_MAX;\n        \n        // option 1 - place carpet\n        \n        if(j<k) // we can only place carpets if we have some remaining black carpets\n            op1=solve(a,i+len,j+1,k,len,dp);\n        \n        // option 2 - dont place the carpet\n        op2=1+solve(a,i+1,j,k,len,dp);\n        \n        \n        return dp[i][j]=min(op1,op2);\n    }\n    \n    return dp[i][j]=solve(a,i+1,j,k,len,dp);\n    \n}\n\nclass Solution {\npublic:\n    int minimumWhiteTiles(string a, int k, int len) {\n        \n        // creating a two dimensional dp array\n        vector<vector<long long int>> dp(a.size()+10,vector<long long int>(k+10,-1));\n        \n        return solve(a,0,0,k,len,dp);\n        \n    }\n};\n\n```\n
['Dynamic Programming', 'Memoization', 'C']