dp | intuition with explaination
Intuition\n\n\nlets suppose are at ith index.\n\nsuppose we are at index i and with j carpets\ndp[i][j] denotes minimum number of uncovered white cells from 0 t
**Intuition**\n\n\nlets suppose are at ith index.\n\nsuppose we are at index i and with j carpets\ndp[i][j] denotes minimum number of uncovered white cells from 0 to i with j \ncarpets.\n\n1. if number of carpets = 0 dp[i][j] = number of carpets from 0 to i.\n\n\nsuppose we are at index i and with j carpets\n1. we dont put carpet. in this case number of uncovered white cells will be \nnumber of uncovered white cells at i-1 +  1 (if ith cell is )\ndp[i][j]  = dp[i-1][j] + 1 if ith carpet is red;\n\n\n2. if we are placing carpet (j>0) such that ith is the last cell covered.\n\ni-carpetlength < 0 that means we are fulling covering from 0 to i.\n[i][j] = 0\n\ni-carpetlength >= 0 that means we are covering from\ni-carpetlength+1 to i and number of carpet left are j-1\n\nso dp[i][j] = dp[i-carpetlength][j-1] // cells i-carpetlength+1 to i is covered\n\nat last we will take minimmum of both the values \ndp[i][j]  = min(dp[i-1][j]) + 1 if ith carpet is red, 0 if i-carpetlength < 0 else dp[i-carpetlength][j-1]\n\n```\nclass Solution {\npublic:\n    int minimumWhiteTiles(string floor, int numCarpets, int carpetLen) {\n        int n = floor.size();\n        vector<vector<int>>dp(n,vector<int>(numCarpets+1));\n        int ans = 0;\n        vector<int>freq(n);\n        for(int i = 0;i<n;i++)\n        {\n            ans += floor[i]-\'0\';\n            freq[i] = ans;\n        }\n        for(int i = 0;i<n;i++)\n        {\n            for(int j = 0;j<=numCarpets;j++)\n            {\n                if(j == 0)\n                {\n                    dp[i][j] = freq[i];\n                    continue;\n                }\n                if(i-carpetLen < 0)\n                {\n                    dp[i][j] = 0;\n                }\n                else if(i-carpetLen >= 0)\n                {\n                    dp[i][j] = dp[i-carpetLen][j-1];\n                }\n                int value = 0;\n                if(i>0)\n                {\n                        value += floor[i]-\'0\';\n                      dp[i][j] = min(dp[i-1][j] + value ,dp[i][j]);\n                }\n                else\n                {\n                      value += floor[i]-\'0\';\n                    dp[i][j] = min(value ,dp[i][j]);\n                }\n          }\n           \n        }\n        return dp[n-1][numCarpets];\n    }\n};\n```
['Dynamic Programming']