min_cost_climbing_stairs

View Source

 1from functools import cache
 2
 3
 4# @leet start
 5class Solution:
 6    def minCostClimbingStairs(self, cost: list[int]) -> int:
 7        """
 8        This question asks us to find the minimum cost of climbing stairs,
 9        where we can climb 1 or 2 stairs at every step, and each step
10        has an associated cost, and we can start from step 0 or 1.
11
12        We can solve this via DP:
13        Take the array of [10, 15, 20, 25, 30]
14        To get to the first step, 10, we pay 0.
15        To get to the second step, 15, we pay 0.
16        For the third step, we can either get there from the first or second
17        step, so we have to either pay the first or second steps' cost.
18
19        For any step `n`, this is the case, you have to pay the minimum steps
20        of all the steps either one before or two before it.
21        So we can use this knowledge to build the DP array:
22
23        With this array:
24        [10, 15, 20, 25, 30]
25        any `n`'s cost is `min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])`.
26
27        So 20's cost would be:
28        20 = min(10 + 0, 15 + 0) = 10
29        25 = min(15 + 0, 10 + 20) = 15
30        30 = min(10 + 20, 15 + 25) = 30
31        top = min(15 + 25, 30 + 30) = 40
32        """
33
34        @cache
35        def min_cost(i):
36            if i <= 1:
37                return 0
38
39            down_one = cost[i - 1] + min_cost(i - 1)
40            down_two = cost[i - 2] + min_cost(i - 2)
41            print(i, min(down_one, down_two))
42            return min(down_one, down_two)
43
44        return min_cost(len(cost))
45
46
47# @leet end
48
49
50def test():
51    assert 2 + 2 == 4

class Solution: View Source

 6class Solution:
 7    def minCostClimbingStairs(self, cost: list[int]) -> int:
 8        """
 9        This question asks us to find the minimum cost of climbing stairs,
10        where we can climb 1 or 2 stairs at every step, and each step
11        has an associated cost, and we can start from step 0 or 1.
12
13        We can solve this via DP:
14        Take the array of [10, 15, 20, 25, 30]
15        To get to the first step, 10, we pay 0.
16        To get to the second step, 15, we pay 0.
17        For the third step, we can either get there from the first or second
18        step, so we have to either pay the first or second steps' cost.
19
20        For any step `n`, this is the case, you have to pay the minimum steps
21        of all the steps either one before or two before it.
22        So we can use this knowledge to build the DP array:
23
24        With this array:
25        [10, 15, 20, 25, 30]
26        any `n`'s cost is `min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])`.
27
28        So 20's cost would be:
29        20 = min(10 + 0, 15 + 0) = 10
30        25 = min(15 + 0, 10 + 20) = 15
31        30 = min(10 + 20, 15 + 25) = 30
32        top = min(15 + 25, 30 + 30) = 40
33        """
34
35        @cache
36        def min_cost(i):
37            if i <= 1:
38                return 0
39
40            down_one = cost[i - 1] + min_cost(i - 1)
41            down_two = cost[i - 2] + min_cost(i - 2)
42            print(i, min(down_one, down_two))
43            return min(down_one, down_two)
44
45        return min_cost(len(cost))

def minCostClimbingStairs(self, cost: list[int]) -> int: View Source

 7    def minCostClimbingStairs(self, cost: list[int]) -> int:
 8        """
 9        This question asks us to find the minimum cost of climbing stairs,
10        where we can climb 1 or 2 stairs at every step, and each step
11        has an associated cost, and we can start from step 0 or 1.
12
13        We can solve this via DP:
14        Take the array of [10, 15, 20, 25, 30]
15        To get to the first step, 10, we pay 0.
16        To get to the second step, 15, we pay 0.
17        For the third step, we can either get there from the first or second
18        step, so we have to either pay the first or second steps' cost.
19
20        For any step `n`, this is the case, you have to pay the minimum steps
21        of all the steps either one before or two before it.
22        So we can use this knowledge to build the DP array:
23
24        With this array:
25        [10, 15, 20, 25, 30]
26        any `n`'s cost is `min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])`.
27
28        So 20's cost would be:
29        20 = min(10 + 0, 15 + 0) = 10
30        25 = min(15 + 0, 10 + 20) = 15
31        30 = min(10 + 20, 15 + 25) = 30
32        top = min(15 + 25, 30 + 30) = 40
33        """
34
35        @cache
36        def min_cost(i):
37            if i <= 1:
38                return 0
39
40            down_one = cost[i - 1] + min_cost(i - 1)
41            down_two = cost[i - 2] + min_cost(i - 2)
42            print(i, min(down_one, down_two))
43            return min(down_one, down_two)
44
45        return min_cost(len(cost))

This question asks us to find the minimum cost of climbing stairs, where we can climb 1 or 2 stairs at every step, and each step has an associated cost, and we can start from step 0 or 1.

We can solve this via DP: Take the array of [10, 15, 20, 25, 30] To get to the first step, 10, we pay 0. To get to the second step, 15, we pay 0. For the third step, we can either get there from the first or second step, so we have to either pay the first or second steps' cost.

For any step n, this is the case, you have to pay the minimum steps of all the steps either one before or two before it. So we can use this knowledge to build the DP array:

With this array: [10, 15, 20, 25, 30] any n's cost is min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]).

So 20's cost would be: 20 = min(10 + 0, 15 + 0) = 10 25 = min(15 + 0, 10 + 20) = 15 30 = min(10 + 20, 15 + 25) = 30 top = min(15 + 25, 30 + 30) = 40

def test(): View Source

51def test():
52    assert 2 + 2 == 4