3693. Climbing Stairs II
- Array
- Dynamic Programming
TIME
O(n)
SPACE
O(1)
Intuition
The cost of landing on step j depends only on where the jump started, and that can only be j - 1, j - 2 or j - 3. So the cheapest way to reach j is the cheapest way to reach one of those three steps, plus the jump. The jump costs costs[j] plus a penalty of 1, 4 or 9 for a jump of length 1, 2 or 3.
Approach
dp[0] = 0. Steps below 0 don't exist, so treat them as unreachable (infinite).- For
j = 1..n:dp[j] = costs[j] + min(dp[j-1] + 1, dp[j-2] + 4, dp[j-3] + 9), wherecostsis 1-indexed as in the statement. - Only the last three values are ever read, so keep three variables and shift them along.
- Return
dp[n].
Complexity
- Time: O(n)
- Space: O(1)
Edge Cases
n = 1: the only move is0 → 1, costingcosts[1] + 1n = 2orn = 3: a single long jump from step 0 can win (example 3), so steps below 0 must be unreachable rather than cost 0- A big jump penalty versus an expensive middle step:
+9for skipping two steps is often still cheaper (example 2 skips step 1 and step 3) - The array is 1-indexed in the statement but 0-indexed in code, so step
jusescosts[j - 1] - The total is at most about
10^5 * (10^4 + 1) ≈ 1.0 * 10^9, which fits in anint
Code
from typing import List
class Solution:
def climbStairs(self, n: int, costs: List[int]) -> int:
"""
3693. Climbing Stairs II
Time: O(n)
Space: O(1)
"""
INF = float("inf")
# a, b, c = best cost to reach steps j - 3, j - 2, j - 1. Steps below 0
# don't exist.
a, b, c = INF, INF, 0
for cost in costs:
a, b, c = b, c, cost + min(c + 1, b + 4, a + 9)
return c/**
* 3693. Climbing Stairs II
* Time: O(n)
* Space: O(1)
*/
class Solution {
public int climbStairs(int n, int[] costs) {
// Large enough to lose every min, small enough that adding 9 can't overflow.
final int INF = Integer.MAX_VALUE / 2;
// a, b, c = best cost to reach steps j - 3, j - 2, j - 1. Steps below 0
// don't exist.
int a = INF, b = INF, c = 0;
for (int cost : costs) {
int next = cost + Math.min(c + 1, Math.min(b + 4, a + 9));
a = b;
b = c;
c = next;
}
return c;
}
}