> For the complete documentation index, see [llms.txt](https://coding-9.gitbook.io/untitled/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://coding-9.gitbook.io/untitled/dynamic-programming/general/2742.-painting-the-walls.md).

# 2742. Painting the Walls

## Problem Statement

<br>

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.*

&#x20;

**Example 1:**

<pre><code><strong>Input: cost = [1,2,3,2], time = [1,2,3,2]
</strong><strong>Output: 3
</strong><strong>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.
</strong></code></pre>

**Example 2:**

<pre><code><strong>Input: cost = [2,3,4,2], time = [1,1,1,1]
</strong><strong>Output: 4
</strong><strong>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.
</strong></code></pre>

&#x20;

**Constraints:**

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

## Intuition

```
Approach:

Here, we maintain the state index, remaining walls

We track the remaining walls like this, at each stage if 
cost painter paints the wall,

We take remaining as 
remain-1(painted by cost one) - time[index](let say paid painter is 
painting for 3 units till this time free painter will paint )

hence remaining will be less
```

### Links

<https://leetcode.com/problems/painting-the-walls/description/>

### Video Links

<https://www.youtube.com/watch?v=qMZJunF5UaI&ab_channel=NeetCodeIO>

### Approach 1:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
class Solution {
public:
    vector<vector<int>> dp;
    int find_ans(vector<int>& cost, vector<int>& time, int index, int remain){
        if(remain <= 0)
            return 0;

        if(index == cost.size())
            return 1e9;
        
        if(dp[index][remain] != -1)
            return dp[index][remain];

        int paint = cost[index] + find_ans(cost, time, index+1, remain-1-time[index]);
        int dont_paint = find_ans(cost, time, index+1, remain);

        return dp[index][remain] = min(paint, dont_paint);
    }

    int paintWalls(vector<int>& cost, vector<int>& time) {
        int n = cost.size();
        dp = vector<vector<int>>(n, vector<int> (n+1, -1));
        return find_ans(cost, time, 0, n);
    }
};
```

{% endcode %}

### Approach 2:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 3:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Approach 4:

```
```

{% code title="C++" lineNumbers="true" %}

```cpp
```

{% endcode %}

### Similar Problems

###