DP solution || Recursion + Memoization
\nclass Solution {\npublic:\n    int solve(int i,string &s,int k,int len,vector<int> &pre,vector<vector<int>> &dp){\n        int n = s.size();\n        if(i>=n)
```\nclass Solution {\npublic:\n    int solve(int i,string &s,int k,int len,vector<int> &pre,vector<vector<int>> &dp){\n        int n = s.size();\n        if(i>=n) return 0;\n        \n        if(dp[i][k]!=-1) return dp[i][k];\n        \n        int tk=-1e9,ksum=0;\n        ksum=(i+len<=n)?(pre[i+len]-pre[i]):(pre[n]-pre[i]);\n        \n        if(k>0 and s[i]==\'1\') tk = ksum+solve(i+len,s,k-1,len,pre,dp);\n        int nottk = 0+solve(i+1,s,k,len,pre,dp);\n        \n        return dp[i][k]=max(tk,nottk);\n    }\n    int minimumWhiteTiles(string s, int numCarpets, int carpetLen) {\n        int n = s.size();\n        vector<int> pre(n+1,0);\n        vector<vector<int>> dp(n+1,vector<int>(numCarpets+1,-1));\n        for(int i=1;i<=n;i++) {\n            pre[i]=pre[i-1];\n            if(s[i-1]==\'1\') pre[i]+=1;\n        }\n        \n        return pre[n]-solve(0,s,numCarpets,carpetLen,pre,dp);\n    }\n};\n```
['Dynamic Programming', 'Memoization']