Giả sử có một cầu thang, bậc thứ i sẽ có chi phí phi âm cost[i] được gán. Khi trả chi phí, ta có thể leo một hoặc hai bậc. Ta cần tìm chi phí tối thiểu để đến đỉnh sàn, và ta cũng có thể bắt đầu từ bậc chỉ số 0 hoặc bậc chỉ số 1.
Ví dụ, nếu đầu vào là cost = [12,17,20], thì đầu ra sẽ là 17, vị trí rẻ nhất để bắt đầu là từ bậc 1 vì ta phải trả chi phí đó và đi đến đỉnh.
Để giải quyết, ta thực hiện các bước sau:
- dp := mảng có kích thước bằng cost, điền 0
- dp[0] := cost[0]
- Nếu kích thước cost >= 2, thì:
- dp[1] := cost[1]
- Với i từ 2 đến kích thước cost - 1, thực hiện:
- dp[i] := cost[i] + min(dp[i-1], dp[i-2])
- Trả về min(dp[-1], dp[-2])
Hãy xem triển khai sau để hiểu rõ hơn:
Ví dụ
class Solution: def minCostClimbingStairs(self, cost): dp = [0] * len(cost) dp[0] = cost[0] if len(cost) >= 2: dp[1] = cost[1] for i in range(2, len(cost)): dp[i] = cost[i] + min(dp[i-1], dp[i-2]) return min(dp[-1], dp[-2]) ob = Solution() print(ob.minCostClimbingStairs([12,17,20]))
Đầu vào
[12,17,20]
Đầu ra
17