Promble
You are given an integer array cost where cost[i] is the cost of ith step on a staircase. Once you pay the cost, you can either climb one or two steps.
You can either start from the step with index 0, or the step with index 1.
Return the minimum cost to reach the top of the floor.
Input: cost = [10,15,20]
Output: 15
Explanation: You will start at index 1.
- Pay 15 and climb two steps to reach the top.
The total cost is 15.
Input: cost = [1,100,1,1,1,100,1,1,100,1]
Output: 6
Explanation: You will start at index 0.
- Pay 1 and climb two steps to reach index 2.
- Pay 1 and climb two steps to reach index 4.
- Pay 1 and climb two steps to reach index 6.
- Pay 1 and climb one step to reach index 7.
- Pay 1 and climb two steps to reach index 9.
- Pay 1 and climb one step to reach the top.
The total cost is 6.
Thought
- total cost记录到当前位置所需要的最少钱
- 状态迁移方程
total cost[i] = min(total cost[i-1], total cost[i-2]) + cost[i]当前cost中的花费+（前一步，或者前两步最小的花费） 这样可以得到当前位置的最优花费 - total cost 和 cost 要多计一位，返回的结果是total cost的最后一位
- 初始状态
total cost[0] = cost[0], total cost[1] = cost[1]因为可以从0或者1的位置开始，所以不需要花费额外的钱，就是当前位置的钱。
Code
class Solution:
def minCostClimbingStairs(self, cost: List[int]) -> int:
# the total cost of current step
total_cost = [0 for _ in range(len(cost)+1)]
total_cost[0] = cost[0]
total_cost[1] = cost[1]
cost.append(0)
print(total_cost)
print(cost)
for i in range(2, len(cost)):
print(i)
total_cost[i] = min(total_cost[i-1], total_cost[i-2]) + cost[i]
print(total_cost)
return total_cost[-1]