Climbing stairs ii

Array Dynamic Programming

64.0% acceptance

Feb 25, 2026

You are climbing a staircase with n + 1 steps, numbered from 0 to n. You are also given a 1-indexed integer array costs of length n, where costs[i] is the cost of step i. From step i, you can jump only to step i + 1, i + 2, or i + 3. The cost of jumping from step i to step j is defined as: costs[j] + (j - i)^2 You start from step 0 with cost = 0. Return the minimum total cost to reach step n.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn climb_stairs(n: i32, costs: Vec<i32>) -> i32 {
    let n = n as usize;
    // dp[i] = min cost to reach step i
    // dp[0] = 0
    // dp[j] = min over i in {j-3, j-2, j-1}: dp[i] + costs[j] + (j-i)^2
    // costs is 1-indexed, so costs[j] = costs[j-1] in 0-indexed
    let mut dp = vec![i64::MAX; n + 1];
    dp[0] = 0;
    for j in 1..=n {
      let cost_j = costs[j - 1] as i64;
      for d in 1..=3 {
        if j >= d {
          let i = j - d;
          if dp[i] < i64::MAX {
            let v = dp[i] + cost_j + (d * d) as i64;
            if v < dp[j] { dp[j] = v; }
          }
        }
      }
    }
    dp[n] as i32
  }
}