2742. Painting the Walls - Explanation

1. Recursion

class Solution:
    def paintWalls(self, cost: List[int], time: List[int]) -> int:

        def dfs(i, remain):
            if remain <= 0:
                return 0
            if i == len(cost):
                return float("inf")

            paint = cost[i] + dfs(i + 1, remain - 1 - time[i])
            skip = dfs(i + 1, remain)
            return min(paint, skip)

        return dfs(0, len(cost))

Time & Space Complexity

Time complexity: $O(2 ^ n)$
Space complexity: $O(n)$ for recursion stack.

2. Dynamic Programming (Top-Down)

class Solution:
    def paintWalls(self, cost: List[int], time: List[int]) -> int:
        dp = {}

        def dfs(i, remain):
            if remain <= 0:
                return 0
            if i == len(cost):
                return float("inf")
            if (i, remain) in dp:
                return dp[(i, remain)]

            paint = cost[i] + dfs(i + 1, remain - 1 - time[i])
            skip = dfs(i + 1, remain)
            dp[(i, remain)] = min(paint, skip)
            return dp[(i, remain)]

        return dfs(0, len(cost))

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n ^ 2)$

3. Dynamic Programming (Bottom-Up)

class Solution:
    def paintWalls(self, cost: List[int], time: List[int]) -> int:
        n = len(cost)
        dp = [[0] * (n + 2) for _ in range(n + 1)]
        for remain in range(1, n + 1):
            dp[n][remain] = float("inf")

        for i in range(n - 1, -1, -1):
            for remain in range(1, n + 1):
                paint = cost[i] + dp[i + 1][max(remain - 1 - time[i], 0)]
                skip = dp[i + 1][remain]
                dp[i][remain] = min(paint, skip)

        return dp[0][n]

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n ^ 2)$

4. Dynamic Programming (Space Optimized)

class Solution:
    def paintWalls(self, cost: List[int], time: List[int]) -> int:
        n = len(cost)
        dp = [float("inf")] * (n + 2)
        dp[0] = 0

        for i in range(n):
            for remain in range(n, 0, -1):
                paint = cost[i] + dp[max(remain - 1 - time[i], 0)]
                dp[remain] = min(paint, dp[remain])

        return dp[n]

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$