Python3 DP Accepted (Is my runtime analysis correct? O(2^N)?)
Below is accepted.\n\nI struggle with figuring out runtime for DP problems, can someone help? \nIs it O(2^N)? My reasoning being that at each backtrack calll, y
Below is accepted.\n\nI struggle with figuring out runtime for DP problems, can someone help? \nIs it O(2^N)? My reasoning being that at each backtrack calll, you either cover the piano, or you don\'t. That\'s 2 choices with at most N steps/piano tiles.\n\nAlso what would be the best way to manually memoize the results without using @lru_cache here?\n\n```\nclass Solution:\n    def minimumWhiteTiles(self, floor: str, numCarpets: int, carpetLen: int) -> int:\n        if numCarpets * carpetLen >= len(floor):\n            return 0\n        \n        white_to_right = [0] * len(floor)\n        for i in range(len(floor)-1, -1, -1):\n            if i == len(floor) - 1:\n                white_to_right[i] = 1 if floor[i] == \'1\' else 0\n            else:\n                white_to_right[i] = white_to_right[i+1]\n                white_to_right[i] += 1 if floor[i] == \'1\' else 0\n        \n        @lru_cache(maxsize=None)\n        def backtrack(index, remaining):\n            if index >= len(floor):\n                return 0\n            \n            if remaining == 0:\n                return white_to_right[index]\n            \n            # cover carpet starting at this index\n            cover_now = backtrack(index + carpetLen, remaining - 1)\n\n            # no-op, cover at next index\n            cover_later = backtrack(index + 1, remaining)\n            cover_later += 1 if floor[index] == \'1\' else 0\n            \n            return min(cover_now, cover_later)\n\n        return backtrack(0, numCarpets)\n\n
[]