Painting the walls

Array Dynamic Programming

48.9% acceptance

Feb 25, 2026

1493

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn paint_walls(cost: Vec<i32>, time: Vec<i32>) -> i32 {
    let n = cost.len();
    // dp[j] = min cost to cover j walls
    let mut dp = vec![i32::MAX / 2; n + 1];
    dp[0] = 0;
    for i in 0..n {
      for j in (1..=n).rev() {
        let skip = (j as i32 - time[i] - 1).max(0) as usize;
        dp[j] = dp[j].min(dp[skip] + cost[i]);
      }
    }
    dp[n]
  }
}