Giả sử chúng ta có một danh sách các số gọi là chiều cao đại diện cho chiều cao của cây và chúng ta có một danh sách các giá trị khác được gọi là chi phí đại diện cho giá cần thiết để tăng chiều cao của một cây. Chúng tôi phải tìm chi phí nhỏ nhất để làm cho mỗi độ cao trong danh sách độ cao khác với các độ cao liền kề.
Vì vậy, nếu đầu vào giống như heights =[3, 2, 2] cost =[2, 5, 3], thì đầu ra sẽ là 3, vì chúng ta có thể tăng chiều cao cuối cùng lên 1, chi phí là 3.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Định nghĩa một hàm dp (). Điều này sẽ lấy idx, l_height
-
nếu idx giống với kích thước chiều cao - 1, thì
-
trả về 0 nếu chiều cao [idx] không giống với l_height, nếu không, giá [idx]
-
-
ret:=inf
-
đối với tôi trong phạm vi từ 0 đến 2, hãy thực hiện
-
nếu chiều cao [idx] + i không giống với l_height thì
-
ret:=tối thiểu ret, dp (idx + 1, heights [idx] + i) + chi phí [idx] * i
-
-
-
trả lại ret
-
Từ phương thức chính trả về dp (0, null)
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
class Solution:
def solve(self, heights, costs):
def dp(idx, l_height):
if idx == len(heights) - 1:
return 0 if heights[idx] != l_height else costs[idx]
ret = float("inf")
for i in range(3):
if heights[idx] + i != l_height:
ret = min(ret, dp(idx + 1, heights[idx] + i) + costs[idx] * i)
return ret
return dp(0, None)
ob = Solution()
heights = [3, 2, 2]
costs = [2, 5, 3]
print(ob.solve(heights, costs)) Đầu vào
[3, 2, 2], [2, 5, 3]
Đầu ra
3