Giả sử có một cầu thang, ở đây bước thứ i sẽ được gán giá trị giá trị chi phí không âm [i] nào đó. Khi chúng ta trả chi phí, chúng ta có thể leo lên một hoặc hai bậc thang. Chúng tôi phải tìm chi phí tối thiểu để đạt đến đỉnh của tầng và chúng tôi cũng có thể bắt đầu từ bước có chỉ số 0 hoặc bước có chỉ số 1.
Vì vậy, nếu đầu vào giống như chi phí =[12,17,20], thì đầu ra sẽ là 17, Vị trí rẻ nhất để bắt đầu từ bước 1 vì chúng ta phải trả chi phí đó và đi lên đầu.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- dp:=một mảng có kích thước tương tự như chi phí và điền bằng 0
- dp [0]:=cost [0]
- nếu quy mô chi phí> =2, thì
- dp [1]:=cost [1]
- đối với tôi trong phạm vi từ 2 đến quy mô chi phí - 1, thực hiện
- dp [i]:=cost [i] + tối thiểu là dp [i-1], dp [i-2]
- trả về tối thiểu dp [-1], dp [-2]
Hãy cùng chúng tôi xem cách 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