# Painting the Walls
**Difficulty:** HARD
[External](https://leetcode.com/problems/painting-the-walls)
Canonical: https://scaleengineer.com/dsa/problems/painting-the-walls
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
**Companies:** [Snowflake](https://scaleengineer.com/companies/snowflake), [DE Shaw](https://scaleengineer.com/companies/de-shaw), [Media.net](https://scaleengineer.com/companies/media.net)
---
## Problem
You are given two **0-indexed** integer arrays, `cost` and `time`, of size `n` representing the costs and the time taken to paint `n` different walls respectively. There are two painters available:

* A **paid painter** that paints the `ith` wall in `time[i]` units of time and takes `cost[i]` units of money.
* A **free painter** that paints **any** wall in `1` unit of time at a cost of `0`. But the free painter can only be used if the paid painter is already **occupied**.

Return _the minimum amount of money required to paint the_ `n` _walls._

**Example 1:**

**Input:** cost = [1,2,3,2], time = [1,2,3,2]
**Output:** 3
**Explanation:** The walls at index 0 and 1 will be painted by the paid painter, and it will take 3 units of time; meanwhile, the free painter will paint the walls at index 2 and 3, free of cost in 2 units of time. Thus, the total cost is 1 + 2 = 3.

**Example 2:**

**Input:** cost = [2,3,4,2], time = [1,1,1,1]
**Output:** 4
**Explanation:** The walls at index 0 and 3 will be painted by the paid painter, and it will take 2 units of time; meanwhile, the free painter will paint the walls at index 1 and 2, free of cost in 2 units of time. Thus, the total cost is 2 + 2 = 4.

**Constraints:**

* `1 <= cost.length <= 500`
* `cost.length == time.length`
* `1 <= cost[i] <= 106`
* `1 <= time[i] <= 500`

# Approaches
## Top-Down Dynamic Programming (Recursion with Memoization)
This problem can be modeled as a variation of the classic 0/1 knapsack problem. For each wall, we have a choice: either pay to paint it or not. If we pay `cost[i]` for wall `i`, we get `1 + time[i]` walls painted (one by the paid painter, `time[i]` by the free painter). Our goal is to select a subset of walls to pay for such that the total number of walls painted is at least `n`, while the total cost is minimized.

A top-down dynamic programming approach using recursion with memoization is a natural way to solve this. We define a function that explores these choices recursively, and we store the results of subproblems to avoid re-computation.
**Time:** O(n^2) - The number of states is `n * (n+1)`. Each state `(i, remain)` is computed once due to memoization, and each computation takes constant time. · **Space:** O(n^2) - The space is dominated by the memoization table `memo` of size `n x (n+1)`. The recursion depth also contributes up to `O(n)` to the call stack space.
**Pros:** The logic directly follows the problem's recursive structure, making it relatively easy to understand and implement.; Guaranteed to find the optimal solution by exploring all valid choices.
**Cons:** The space complexity is `O(n^2)`, which might be high for very large `n`.; Recursive solutions can lead to a `StackOverflowError` for deep recursion chains, although `n=500` is generally safe in most environments.; Typically has higher constant factor overhead compared to iterative solutions due to function call stacks.
### Explanation
We define a recursive function `solve(i, remain)` that computes the minimum cost to paint `remain` more walls, given that we can choose from walls `i` through `n-1`. The state of our recursion is defined by the current wall index `i` and the number of walls `remain` that still need to be painted.

For each wall `i`, we explore two possibilities: we either pay for it or we don't. 
- If we pay for wall `i`, we incur `cost[i]`, and the number of walls we still need to paint decreases by `1 + time[i]`. The total cost for this branch is `cost[i]` plus the result of the recursive call for the next wall: `solve(i + 1, remain - 1 - time[i])`.
- If we don't pay for wall `i`, the cost is simply the result of the recursive call for the next wall with the same remaining walls: `solve(i + 1, remain)`.

The minimum of these two outcomes is the answer for the state `(i, remain)`. The base cases for the recursion are when `remain <= 0` (we're done, cost is 0) or when we run out of walls (`i == n`) but still have walls to paint (an invalid path, cost is infinity).

To make this efficient, we store the results for each state `(i, remain)` in a 2D memoization table. This ensures that each subproblem is solved only once.

```java
import java.util.Arrays;

class Solution {
    private int[][] memo;
    private int[] cost;
    private int[] time;
    private int n;

    public int paintWalls(int[] cost, int[] time) {
        this.n = cost.length;
        this.cost = cost;
        this.time = time;
        this.memo = new int[n][n + 1];
        for (int[] row : memo) {
            Arrays.fill(row, -1);
        }
        return solve(0, n);
    }

    private int solve(int i, int remain) {
        if (remain <= 0) {
            return 0;
        }
        if (i == n) {
            return 1_000_000_007; // A large value representing infinity
        }
        if (memo[i][remain] != -1) {
            return memo[i][remain];
        }

        // Option 1: Paint wall i
        int paintOption = cost[i] + solve(i + 1, remain - 1 - time[i]);

        // Option 2: Skip wall i
        int skipOption = solve(i + 1, remain);

        return memo[i][remain] = Math.min(paintOption, skipOption);
    }
}
```
### Algorithm
1.  Define a recursive function, let's call it `solve(i, remain)`, which calculates the minimum cost to paint `remain` walls using the walls from index `i` to `n-1`.
2.  **Base Cases**:
    *   If `remain <= 0`, it means we have successfully painted at least `n` walls. The cost for this is 0, so we return 0.
    *   If `i == n` (we've considered all walls) but `remain > 0`, it's impossible to paint the remaining walls. We return a very large value (infinity) to indicate that this path is not a valid solution.
3.  **Recursive Step**: For the wall at index `i`, we have two choices:
    *   **Paint wall `i`**: We pay `cost[i]`. This action paints wall `i` and allows the free painter to work for `time[i]` units, painting `time[i]` additional walls. In total, `1 + time[i]` walls are covered. The cost for this choice is `cost[i] + solve(i + 1, remain - 1 - time[i])`.
    *   **Skip wall `i`**: We don't pay for wall `i`. The cost is determined by the choices for the remaining walls, which is `solve(i + 1, remain)`.
4.  The function `solve(i, remain)` returns the minimum of the costs from these two choices.
5.  **Memoization**: To avoid redundant calculations for the same state `(i, remain)`, we use a 2D array `memo` (e.g., of size `n x (n+1)`). Before computing, we check if `memo[i][remain]` has already been calculated. If so, we return the stored value. Otherwise, we compute the result, store it in the memo table, and then return it.
6.  The initial call to start the process is `solve(0, n)`.

## Bottom-Up Dynamic Programming (2D Table)
An alternative to the top-down recursive approach is a bottom-up iterative approach. This method systematically builds up the solution from the smallest subproblems to the final problem. We use a 2D array to store the results of subproblems, effectively turning the recursion into iteration. This avoids recursion overhead and the risk of stack overflow.
**Time:** O(n^2) - We iterate through the `dp` table using two nested loops of size `n`. · **Space:** O(n^2) - Requires a 2D DP table of size `(n+1) x (n+1)`.
**Pros:** Avoids recursion, eliminating the risk of stack overflow and reducing function call overhead.; The logic is systematic and can be easier to debug than a recursive solution.
**Cons:** The `O(n^2)` space complexity can be a concern for memory-constrained environments.; It is less space-efficient than the optimized 1D DP approach.
### Explanation
We create a 2D DP table, `dp`, where `dp[i][j]` represents the minimum cost to paint at least `j` walls using the first `i` walls (from index 0 to `i-1`). The table size will be `(n+1) x (n+1)`.

We initialize `dp[0][0]` to 0 and the rest of the first row `dp[0][j]` to infinity. Then, we iterate from `i = 1` to `n`. For each wall `i-1`, we iterate through the target number of painted walls `j` from 1 to `n`. At each cell `dp[i][j]`, we decide whether to include wall `i-1` in our set of paid walls.

- The cost if we **don't** pay for wall `i-1` is simply `dp[i-1][j]`. 
- The cost if we **do** pay for wall `i-1` is `cost[i-1]` plus the cost to cover the remaining walls. Since wall `i-1` covers `1 + time[i-1]` walls, we need to find the cost of covering `j - (1 + time[i-1])` walls using the first `i-1` walls. This is given by `dp[i-1][max(0, j - 1 - time[i-1])]`.

We take the minimum of these two options to populate `dp[i][j]`. After filling the entire table, the value `dp[n][n]` gives the minimum cost to paint at least `n` walls using all available walls.

```java
import java.util.Arrays;

class Solution {
    public int paintWalls(int[] cost, int[] time) {
        int n = cost.length;
        long[][] dp = new long[n + 1][n + 1];
        long infinity = Long.MAX_VALUE / 2; // Use a large value that doesn't overflow on addition

        for (int j = 1; j <= n; j++) {
            dp[0][j] = infinity;
        }
        // dp[i][0] is 0 for all i, which is the default

        for (int i = 1; i <= n; i++) {
            int c = cost[i - 1];
            int t = time[i - 1];
            for (int j = 1; j <= n; j++) {
                long paintOption = c + dp[i - 1][Math.max(0, j - 1 - t)];
                long skipOption = dp[i - 1][j];
                dp[i][j] = Math.min(paintOption, skipOption);
            }
        }

        return (int) dp[n][n];
    }
}
```
### Algorithm
1.  Create a 2D DP table, `dp`, of size `(n+1) x (n+1)`.
2.  `dp[i][j]` will store the minimum cost to paint at least `j` walls using the first `i` walls.
3.  **Initialization**:
    *   Set `dp[0][0] = 0`, as it costs nothing to paint 0 walls with no walls available.
    *   Initialize all `dp[0][j]` for `j > 0` to a large value (infinity), since it's impossible to paint walls without any to choose from.
    *   `dp[i][0]` for all `i` will be 0, as painting 0 walls always costs 0.
4.  **Iteration**:
    *   Loop through each wall `i` from 1 to `n`.
    *   Inside this loop, loop through the number of walls to paint, `j`, from 1 to `n`.
    *   For each `dp[i][j]`, calculate the cost based on two choices for wall `i-1`:
        *   **Skip wall `i-1`**: The cost is inherited from the previous state, `dp[i-1][j]`.
        *   **Paint wall `i-1`**: The cost is `cost[i-1]` plus the cost to paint the remaining walls. Since painting wall `i-1` covers `1 + time[i-1]` walls, we look up the cost from `dp[i-1][max(0, j - 1 - time[i-1])]`.
    *   The state transition is: `dp[i][j] = min(dp[i-1][j], cost[i-1] + dp[i-1][max(0, j - 1 - time[i-1])])`.
5.  **Result**: The final answer is `dp[n][n]`, which represents the minimum cost to paint at least `n` walls using all `n` available walls.

## Space-Optimized Bottom-Up Dynamic Programming (1D Table)
The most efficient approach in terms of memory is a space-optimized version of the bottom-up DP. Observing the recurrence relation `dp[i][j] = min(dp[i-1][j], ...)`, we can see that computing the values for the current row `i` only requires values from the previous row `i-1`. This dependency allows us to reduce the space complexity from `O(n^2)` to `O(n)` by using only a single 1D array.
**Time:** O(n^2) - The algorithm uses two nested loops. The outer loop runs `n` times (for each wall), and the inner loop runs `n` times (for each possible number of walls to paint). · **Space:** O(n) - We only need a 1D array of size `n+1` to store the DP states.
**Pros:** Highly space-efficient, with `O(n)` space complexity.; Maintains the `O(n^2)` time efficiency of the other DP approaches.; Iterative nature avoids recursion overhead, making it very fast in practice.
**Cons:** The logic of iterating the inner loop backwards can be less intuitive at first glance compared to the 2D DP approach.
### Explanation
This approach refines the 2D DP solution by using a single 1D array, `dp`, of size `n+1`. Here, `dp[j]` stores the minimum cost to paint at least `j` walls, considering the walls processed so far.

We initialize `dp[0]` to 0 and the rest of the array to infinity. We then iterate through each wall. For each wall `i` with `cost[i]` and `time[i]`, we update the `dp` array. The key insight is to iterate the inner loop (for `j`) from `n` down to 1. 

When we calculate the new value for `dp[j]`, we consider two options:
1.  **Don't paint wall `i`**: The cost to paint `j` walls remains `dp[j]` (its value from before this iteration).
2.  **Paint wall `i`**: The cost is `cost[i]` plus the cost to paint the remaining `j - (1 + time[i])` walls. This previous cost is found at `dp[max(0, j - 1 - time[i])]`.

By iterating `j` backwards, we ensure that when we access `dp[k]` where `k < j`, we are accessing the value from the previous outer loop iteration (i.e., without considering wall `i`). This correctly mimics the behavior of using `dp[i-1]` from the 2D table. After iterating through all walls, `dp[n]` will hold the minimum cost to paint at least `n` walls.

```java
import java.util.Arrays;

class Solution {
    public int paintWalls(int[] cost, int[] time) {
        int n = cost.length;
        int[] dp = new int[n + 1];
        int infinity = 1_000_000_007;
        Arrays.fill(dp, infinity);
        dp[0] = 0;

        for (int i = 0; i < n; i++) {
            int c = cost[i];
            int t = time[i];
            for (int j = n; j > 0; j--) {
                int prevIndex = Math.max(0, j - 1 - t);
                if (dp[prevIndex] != infinity) {
                    dp[j] = Math.min(dp[j], dp[prevIndex] + c);
                }
            }
        }

        return dp[n];
    }
}
```
### Algorithm
1.  Create a 1D DP array, `dp`, of size `n+1`.
2.  `dp[j]` will store the minimum cost to paint at least `j` walls.
3.  **Initialization**:
    *   Set `dp[0] = 0`.
    *   Initialize all other elements `dp[j]` for `j > 0` to a large value (infinity).
4.  **Iteration**:
    *   Loop through each wall `i` from 0 to `n-1`.
    *   Inside this loop, have a second loop for `j` that iterates backwards, from `n` down to 1.
    *   The update rule is `dp[j] = min(dp[j], cost[i] + dp[previous_j])`, where `previous_j = max(0, j - 1 - time[i])`.
    *   Iterating `j` backwards is crucial. It ensures that when we calculate the new `dp[j]` using `dp[previous_j]`, the value `dp[previous_j]` is from the state *before* considering wall `i` (equivalent to `dp[i-1]` in the 2D version).
5.  **Result**: After iterating through all the walls, the answer is `dp[n]`.

# Solutions
### Java

```java
class Solution {
private
  int n;
private
  int[] cost;
private
  int[] time;
private
  Integer[][] f;
public
  int paintWalls(int[] cost, int[] time) {
    n = cost.length;
    this.cost = cost;
    this.time = time;
    f = new Integer[n][n << 1 | 1];
    return dfs(0, n);
  }
private
  int dfs(int i, int j) {
    if (n - i <= j - n) {
      return 0;
    }
    if (i >= n) {
      return 1 << 30;
    }
    if (f[i][j] == null) {
      f[i][j] = Math.min(dfs(i + 1, j + time[i]) + cost[i], dfs(i + 1, j - 1));
    }
    return f[i][j];
  }
}

```

### CPP

```cpp
class Solution {
public:
  int paintWalls(vector<int> &cost, vector<int> &time) {
    int n = cost.size();
    int f[n][n << 1 | 1];
    memset(f, -1, sizeof(f));
    function<int(int, int)> dfs = [&](int i, int j) -> int {
      if (n - i <= j - n) {
        return 0;
      }
      if (i >= n) {
        return 1 << 30;
      }
      if (f[i][j] == -1) {
        f[i][j] = min(dfs(i + 1, j + time[i]) + cost[i], dfs(i + 1, j - 1));
      }
      return f[i][j];
    };
    return dfs(0, n);
  }
};

```

### Python

```python
class Solution:
    def paintWalls(self, cost: List[int], time: List[int]) -> int: @ cache def dfs(i: int, j: int) -> int: if n - i <= j: return 0 if i >= n: return inf return min(dfs(i + 1, j + time[i]) + cost[i], dfs(i + 1, j - 1)) n = len(cost) return dfs(0, 0)

```