Skip to content

2742. Painting the Walls 👍

Approach 1: Top-down

  • Time: $O(n^2)$
  • Space: $O(n^2)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
 public:
  int paintWalls(vector<int>& cost, vector<int>& time) {
    const int n = cost.size();
    // dp[i][j] := min cost to paint j walls by first painters[i:]
    dp.resize(n, vector<int>(n + 1));
    return paintWalls(cost, time, 0, time.size());
  }

 private:
  static constexpr int kMax = 500'000'000;
  vector<vector<int>> dp;

  int paintWalls(const vector<int>& cost, const vector<int>& time, int i,
                 int walls) {
    if (walls <= 0)
      return 0;
    if (i == cost.size())
      return kMax;
    if (dp[i][walls] > 0)
      return dp[i][walls];
    const int pick =
        cost[i] + paintWalls(cost, time, i + 1, walls - time[i] - 1);
    const int skip = paintWalls(cost, time, i + 1, walls);
    return dp[i][walls] = min(pick, skip);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
  public int paintWalls(int[] cost, int[] time) {
    final int n = cost.length;
    dp = new int[n][n + 1];
    return paintWalls(cost, time, 0, time.length);
  }

  private static final int kMax = 500_000_000;
  private int[][] dp;

  private int paintWalls(int[] cost, int[] time, int i, int walls) {
    if (walls <= 0)
      return 0;
    if (i == cost.length)
      return kMax;
    if (dp[i][walls] > 0)
      return dp[i][walls];
    final int pick = cost[i] + paintWalls(cost, time, i + 1, walls - time[i] - 1);
    final int skip = paintWalls(cost, time, i + 1, walls);
    return dp[i][walls] = Math.min(pick, skip);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
  def paintWalls(self, cost: List[int], time: List[int]) -> int:
    n = len(cost)

    # dp(i, j) := min cost to paj walls by first painters[i:]
    @functools.lru_cache(None)
    def dp(i: int, walls: int) -> int:
      if walls <= 0:
        return 0
      if i == n:
        return math.inf
      pick = cost[i] + dp(i + 1, walls - time[i] - 1)
      skip = dp(i + 1, walls)
      return min(pick, skip)

    return dp(0, n)

Approach 2: Bottom-up

  • Time: $O(n^2)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
 public:
  int paintWalls(vector<int>& cost, vector<int>& time) {
    constexpr int kMax = 500'000'000;
    const int n = cost.size();
    // dp[i] := min cost to paint i walls by painters so far
    vector<int> dp(n + 1, kMax);
    dp[0] = 0;

    for (int i = 0; i < n; ++i)
      for (int walls = n; walls > 0; --walls)
        dp[walls] = min(dp[walls], dp[max(walls - time[i] - 1, 0)] + cost[i]);

    return dp[n];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
  public int paintWalls(int[] cost, int[] time) {
    final int kMax = 500_000_000;
    final int n = cost.length;
    // dp[i] := min cost to paint i walls by painters so far
    int[] dp = new int[n + 1];
    Arrays.fill(dp, kMax);
    dp[0] = 0;

    for (int i = 0; i < n; ++i)
      for (int walls = n; walls > 0; --walls)
        dp[walls] = Math.min(dp[walls], dp[Math.max(walls - time[i] - 1, 0)] + cost[i]);

    return dp[n];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
  def paintWalls(self, cost: List[int], time: List[int]) -> int:
    kMax = 500_000_000
    n = len(cost)
    # dp[i] := min cost to paint i walls by painters so far
    dp = [0] + [kMax] * n

    for c, t in zip(cost, time):
      for walls in range(n, 0, -1):
        dp[walls] = min(dp[walls], dp[max(walls - t - 1, 0)] + c)

    return dp[n]