Description #
On a staircase, the i-th step has some non-negative cost cost[i] assigned (0 indexed).
Once you pay the cost, you can either climb one or two steps. You need to find minimum cost to reach the top of the floor, and you can either start from the step with index 0, or the step with index 1.
Example 1:
Input: cost = [10, 15, 20] Output: 15 Explanation: Cheapest is start on cost[1], pay that cost and go to the top.Example 2:
Input: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] Output: 6 Explanation: Cheapest is start on cost[0], and only step on 1s, skipping cost[3].Note:
- cost will have a length in the range [2, 1000].
- Every cost[i] will be an integer in the range [0, 999].
(From the problem description)
Test Vectors #
| stairs | minimum cost | steps |
|---|---|---|
| [10, 15, 20] | 15 | [1] |
| [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] | 6 | [0, 2, 4, 6, 7, 9] |
Problem Analysis #
This problem lends itself especially good to dynamic programming:
- It has optimal sub-problems: What is the cheapest way to get to step
n-1? - The sub problems are overlapping, meaning: they can be used multiple times.
Given is a cost vector \(cost\) with length \(n\): \(cost := [1, 3, 5, 7]\).
\(optimal_a\) is the optimal cost to reach step \(a\). E.g. \(optimal_0\) trivially is \(0\) (because we can directly jump there, so is \(optimal_1\)). \(optimal_2\) is \(1\) and \(optimal_3\) is \(3\). Sought is \(optimal_n\) (“after the array ends”).
If we know the optimal cost for \(n - 1\) and \(n - 2\), then the optimal cost for \(n\) is \(min(optimal_{n-2} + cost_{n-2}, optimal_{n-1} + cost_{n-1})\).
I’ll try three solutions that build on each other:
-
A naive recursive solution that is a direct transcription of the problem statement. Unfortunately it has exponential time complexity \(O(2^n)\).
-
Building on that a version that uses dynamic programming to memorize the optimal cost for a given step instead of calculating it over and over again. This brings down time complexity to \(O(n)\) but introduces a space complexity of \(O(n)\).
-
The recursive solution can be transformed into an incremental solution with \(O(n)\) runtime and \(O(1)\) space complexity.
For a better visualization of the runtime complexity benchmarks for lists of the lengths 5, 10, 20, 24, 28, and 32 are calculated.
Solutions #
The tests are trivial and not shown.
Solution 1: Recursive #
from typing import List
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
if len(cost) == 1:
# Skip the first element
return 0
elif len(cost) == 2:
return min(cost[0], cost[1])
else:
cost_1 = cost[-1] + self.minCostClimbingStairs(cost[:-1])
cost_2 = cost[-2] + self.minCostClimbingStairs(cost[:-2])
return min(cost_1, cost_2 )
Test Results #
With the following test result:
============================= test session starts ==============================
platform linux -- Python 3.7.5, pytest-3.10.1, py-1.8.0, pluggy-0.12.0
benchmark: 3.2.2 (defaults: timer=time.perf_counter disable_gc=False min_rounds=5 min_time=0.000005 max_time=1.0 calibration_precision=10 warmup=False warmup_iterations=100000)
rootdir: /home/jens/Documents/leetcode.com/746-Min-Cost-Climbing-Stairs, inifile:
plugins: benchmark-3.2.2, profiling-1.7.0
collected 5 items
test_1a-solution.py ..... [100%]
============================ slowest test durations ============================
(0.00 durations hidden. Use -vv to show these durations.)
=========================== 5 passed in 0.03 seconds ===========================
Tests ran in 0.18452599000011105 seconds
Analysis #
The results are correct, but the runtime is very, very bad. In fact, the runtime complexity is exponential to the length of the list: \(O(2^n)\). This can be improved by memorizing the optimal solutions \(optimal_{0..n-1}\).
Solution 2: Dynamic programming with a memorizing #
from typing import List
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
self.optimal = [ None for x in range(0, len(cost) + 1)]
self.optimal[0] = 0
self.optimal[1] = 0
return self._minCostClimbingStairs(cost)
def _minCostClimbingStairs(self, cost: List[int]) -> int:
if self.optimal[len(cost)] is None:
cost_1 = cost[-1] + self._minCostClimbingStairs(cost[:-1])
cost_2 = cost[-2] + self._minCostClimbingStairs(cost[:-2])
self.optimal[len(cost)] = min(cost_1, cost_2 )
return self.optimal[len(cost)]
Test Results #
With the following test result:
============================= test session starts ==============================
platform linux -- Python 3.7.5, pytest-3.10.1, py-1.8.0, pluggy-0.12.0
benchmark: 3.2.2 (defaults: timer=time.perf_counter disable_gc=False min_rounds=5 min_time=0.000005 max_time=1.0 calibration_precision=10 warmup=False warmup_iterations=100000)
rootdir: /home/jens/Documents/leetcode.com/746-Min-Cost-Climbing-Stairs, inifile:
plugins: benchmark-3.2.2, profiling-1.7.0
collected 5 items
test_1b-solution.py ..... [100%]
============================ slowest test durations ============================
(0.00 durations hidden. Use -vv to show these durations.)
=========================== 5 passed in 0.02 seconds ===========================
Tests ran in 0.17106291800155304 seconds
Analysis #
This is much better: \(O(n)\) runtime complexity and \(O(n)\) space complexity. Still not ideal though: Instead of a top down, recursive approach we can work ourselves “upwards” with a space complexity of \(O(1)\).
Solution 3: Dynamic programming #
from typing import List
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
# instead of opt_minus_1/2 we could just update the
# cost array and incrementally convert it into an
# array with the optimal solution.
# Since changing the input parameters is a code smell
# I'll use local variables.
opt_minus_1 = 0
opt_minus_2 = 0
for i in range(2, len(cost) + 1):
a = min(opt_minus_1 + cost[i-1], opt_minus_2 + cost[i-2])
opt_minus_2 = opt_minus_1
opt_minus_1 = a
return opt_minus_1
Test Results #
With the following test result:
============================= test session starts ==============================
platform linux -- Python 3.7.5, pytest-3.10.1, py-1.8.0, pluggy-0.12.0
benchmark: 3.2.2 (defaults: timer=time.perf_counter disable_gc=False min_rounds=5 min_time=0.000005 max_time=1.0 calibration_precision=10 warmup=False warmup_iterations=100000)
rootdir: /home/jens/Documents/leetcode.com/746-Min-Cost-Climbing-Stairs, inifile:
plugins: benchmark-3.2.2, profiling-1.7.0
collected 5 items
test_1c-solution.py ..... [100%]
============================ slowest test durations ============================
(0.00 durations hidden. Use -vv to show these durations.)
=========================== 5 passed in 0.02 seconds ===========================
Tests ran in 0.17213164499844424 seconds
Analysis #
This solution is even better than the previous one. There is still some room for improvement but the main point here was to get to a \(O(n)\) time / \(O(1)\) space complexity.
Summary #
All solutions work (except #1 which leads to a timeout for large data sets).
| Solution | Correct | Status | Runtime | Memory | Language |
|---|---|---|---|---|---|
| Solution#3 | Yes | Submission | 60 ms, faster than 44.27% | 12.7 MB, less than 100.00% | Python3 |