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
class Solution {
 public:
  int paintWalls(vector<int>& cost, vector<int>& time) {
    const int n = cost.size();
    vector<vector<int>> mem(n, vector<int>(n + 1));
    return paintWalls(cost, time, 0, time.size(), mem);
  }

 private:
  static constexpr int kMax = 500'000'000;

  // Returns the minimum cost to paint j walls by painters[i..n).
  int paintWalls(const vector<int>& cost, const vector<int>& time, int i,
                 int walls, vector<vector<int>>& mem) {
    if (walls <= 0)
      return 0;
    if (i == cost.size())
      return kMax;
    if (mem[i][walls] > 0)
      return mem[i][walls];
    const int pick =
        cost[i] + paintWalls(cost, time, i + 1, walls - time[i] - 1, mem);
    const int skip = paintWalls(cost, time, i + 1, walls, mem);
    return mem[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;
    int[][] mem = new int[n][n + 1];
    return paintWalls(cost, time, 0, time.length, mem);
  }

  private static final int kMax = 500_000_000;

  // Returns the minimum cost to paint j walls by painters[i..n).
  private int paintWalls(int[] cost, int[] time, int i, int walls, int[][] mem) {
    if (walls <= 0)
      return 0;
    if (i == cost.length)
      return kMax;
    if (mem[i][walls] > 0)
      return mem[i][walls];
    final int pick = cost[i] + paintWalls(cost, time, i + 1, walls - time[i] - 1, mem);
    final int skip = paintWalls(cost, time, i + 1, walls, mem);
    return mem[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)

    @functools.lru_cache(None)
    def dp(i: int, walls: int) -> int:
      """Returns the minimum cost to paint j walls by painters[i..n)."""
      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] := the minimum cost to paint i walls by the 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] := the minimum cost to paint i walls by the 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] := the minimum cost to paint i walls by the 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]