Easy DP explanation with intuition | Memo | Recursion |  Bottom-up | Top Down
Intuition\n Describe your first thoughts on how to solve this problem. \nIf it was a continous carpets question, this could probably solved by sliding window wh
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nIf it was a continous carpets question, this could probably solved by sliding window which were my first thoughts. Later understood that the carpets can be placed anywhere so this becomes including excluding recursion problem.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- If you want to add a carpet at certain integer then you will cover index+carpetLen values as well with one less carpet. So now we need visible tile count of subProblem (i+1,j-1) i being the floor index and j being the carpet count.\n- If you decide not to include a carpet then it means the current integer if its a 1 is visible + the remaining subProblem with same amount of tiles i.e., i+1,j \n- Min of the above two paths is stored in memo\n- Note for basic reference :for top down dp you have i as emptyString\'\'+floor and j->0 to carpets .for bottom up you have floor+emptyString and j->carpets to 0\n- so at dp[i][j] you will store visible tiles at i with j number of tiles\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(floor.length*numOfCarpets)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(floor.length*numOfCarpets)\n\n# Code\nRecursion & Memoization (TLE, just for reference)\n```\n/**\n * @param {string} floor\n * @param {number} numCarpets\n * @param {number} carpetLen\n * @return {number}\n */\nvar minimumWhiteTiles = function (floor, numCarpets, carpetLen) {\n  let dp = new Array(floor.length);\n\n    for (let i = 0; i < dp.length; i++) {\n        dp[i] = new Array(numCarpets.length);\n    }\n\n    let suffixCount = new Array(floor.length).fill(0);\n    suffixCount[floor.length - 1] = floor[floor.length - 1] == \'1\' ? 1 : 0;\n\n    for (let i = floor.length - 2; i >= 0; i--) {\n        suffixCount[i] = suffixCount[i + 1] + (floor[i] == \'1\');\n    }\n\n    let helper = function (index, carpsLeft) {\n        if (index >= floor.length) {\n            return 0;\n        }\n        if (dp[index] && dp[index][carpsLeft]) return dp[index][carpsLeft];\n        if (carpsLeft == 0) {\n            return suffixCount[index];\n        }\n\n        let addCarpet = helper(index + carpetLen, carpsLeft - 1);\n        let noCarpet = (floor[index] == 1) + helper(index + 1, carpsLeft);\n\n        dp[index][carpsLeft] = Math.min(addCarpet, noCarpet);\n\n        return dp[index][carpsLeft];\n    }\n\n    return helper(0, numCarpets);\n  }\n\n};\n\n```\nTop Down approach\n```\nvar minimumWhiteTiles = function (floor, numCarpets, carpetLen) {\n    let dp = new Array(floor.length + 1);\n    for (let i = 0; i < dp.length; i++) {\n        dp[i] = new Array(numCarpets + 1)\n    }\n\n    for (let i = 0; i < dp.length; i++) {\n         for (let j = 0; j < dp[0].length; j++) {\n             if ((i == 0 && j == 0) || i == 0) dp[i][j] = 0;\n            else if (j == 0) {\n                dp[i][j] = floor[i - 1] == \'1\' ? 1 + dp[i - 1][j] : dp[i - 1][j];\n            }\n            else {\n                let addCarpet = 0;\n                if (i >= carpetLen) addCarpet = dp[i - carpetLen][j - 1];\n                let noCarpet = floor[i - 1] == \'1\' ? 1 + dp[i - 1][j] : dp[i - 1][j];\n                dp[i][j] = Math.min(addCarpet, noCarpet);\n            }\n        }\n    }\n\n    return dp[floor.length][numCarpets]\n  }\n```\nBottom-Up approach\n```\nvar minimumWhiteTiles = function (floor, numCarpets, carpetLen) {\n  let dp = new Array(floor.length + 1);\n  for (let i = 0; i < dp.length; i++) {\n      dp[i] = new Array(numCarpets + 1).fill(0)\n  }\n\n  let m = dp.length;\n  let n = dp[0].length;\n\n  for (let i = m - 1; i >= 0; i--) {\n      for (let j = n - 1; j >= 0; j--) {\n          if ((i == m - 1 && j == n - 1) || i == m - 1) dp[i][j] = 0;\n          else if (j == n - 1) {\n              dp[i][j] = floor[i] == \'1\' ? 1 + dp[i + 1][j] : dp[i + 1][j];\n          }\n          else {\n              let addCarpet = 0;\n              //the carpet will cover the length so we just need to consider visible values after that index with less carpets\n              if (i + carpetLen < m) addCarpet = dp[i + carpetLen][j + 1];\n              //if we are not considering to add carpet then just check next index value with same carpets\n              let noCarpet = floor[i] == \'1\' ? 1 + dp[i + 1][j] : dp[i + 1][j];\n              dp[i][j] = Math.min(addCarpet, noCarpet);\n          }\n      }\n  }\n\n  return dp[0][0];\n  }\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n```
['String', 'Dynamic Programming', 'Prefix Sum', 'JavaScript']