LeetCode #746 : Min cost climbing stairs
60 ms, faster than 44.27%
Description
On a staircase, the ith step has some nonnegative 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 subproblems: What is the cheapest way to get to step
n1
?  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_{n2} + cost_{n2}, optimal_{n1} + cost_{n1})\).
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, pytest3.10.1, py1.8.0, pluggy0.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/746MinCostClimbingStairs, inifile:
plugins: benchmark3.2.2, profiling1.7.0
collected 5 items
test_1asolution.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..n1}\).
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, pytest3.10.1, py1.8.0, pluggy0.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/746MinCostClimbingStairs, inifile:
plugins: benchmark3.2.2, profiling1.7.0
collected 5 items
test_1bsolution.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[i1], opt_minus_2 + cost[i2])
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, pytest3.10.1, py1.8.0, pluggy0.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/746MinCostClimbingStairs, inifile:
plugins: benchmark3.2.2, profiling1.7.0
collected 5 items
test_1csolution.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 