DDSA Solutions

3693. Climbing Stairs II

MediumView on LeetCode
ArrayDynamic Programming
Time: O(n)
Space: O(1)

Problem Overview

Steps are numbered from 0 to n, and the cost array stores the cost of steps 1 through n.

Intuition

Steps are numbered from 0 to n, and the cost array stores the cost of steps 1 through n. From any step you may jump forward by 1, 2, or 3. Landing on step i after a jump of distance d costs costs[i - 1] plus d squared. The cheapest way to reach step i therefore depends only on the cheapest ways to reach i minus 1, i minus 2, and i minus 3. Those three candidates are compared for every i from 1 to n. Only the previous three answers are kept, so the walk uses constant extra space. The value at step n is the answer. Step 0 starts at cost 0 and is never charged a landing cost.

Algorithm

  1. 1Keep three rolling values a, b, and c for steps i minus 3, i minus 2, and i minus 1, with c starting at 0 for step 0.
  2. 2For each step i from 1 to n, read costs[i - 1].
  3. 3Build the next cost as the minimum of c plus cost plus 1, b plus cost plus 4, and a plus cost plus 9, skipping any predecessor that is still unreachable.
  4. 4Shift a, b, and c forward and continue.
  5. 5Return c after step n.

Example Walkthrough

Input: n = 4, costs = [1, 2, 3, 4]

  1. 1.Step 1 costs 1 plus 1 from step 0, so the running total is 2.
  2. 2.Step 2 can come from step 1 for 3 more, totaling 5, or from step 0 for 2 plus 4, totaling 6. The cheaper total is 5.
  3. 3.An optimal path is 0 to 1 to 2 to 4. The last jump adds 4 plus 4, so the total is 13.

Output: 13

Common Pitfalls

  • •costs is 0-indexed in code. The cost of step i is costs[i - 1].
  • •The jump surcharge is the square of the distance. A jump of 2 adds 4, and a jump of 3 adds 9.
  • •Do not charge a cost for standing on step 0. The walk begins there for free.
  • •Only three previous states are needed. Allocating a full dp array of length n plus 1 is unnecessary.
3693.cs
C#
// Approach: dp[i] is the cheapest way to reach step i. A jump from i - d
// costs costs[i - 1] plus d squared for d in 1, 2, 3. Only the previous three
// dp values are needed, so they roll forward in constant space.
// Time: O(n) Space: O(1)

public class Solution
{
    public int ClimbStairs(int n, int[] costs)
    {
        const int Inf = int.MaxValue / 4;
        int a = Inf, b = Inf, c = 0;

        for (int i = 1; i <= n; i++)
        {
            int cost = costs[i - 1];
            int next = Inf;
            if (c != Inf)
                next = Math.Min(next, c + cost + 1);
            if (b != Inf)
                next = Math.Min(next, b + cost + 4);
            if (a != Inf)
                next = Math.Min(next, a + cost + 9);
            a = b;
            b = c;
            c = next;
        }

        return c;
    }
}
Was this solution helpful?

Related Problems