식물의 높이를 나타내는 높이라는 숫자 목록이 있고 식물의 높이를 1 높이는 데 필요한 가격을 나타내는 비용이라는 값의 또 다른 목록이 있다고 가정합니다. 높이 목록의 각 높이를 인접한 높이와 다르게 만들기 위해 가장 작은 비용을 찾아야 합니다.
따라서 입력이 height =[3, 2, 2] 비용 =[2, 5, 3]과 같으면 출력은 3이 됩니다. 마지막 높이를 1만큼 늘릴 수 있으므로 비용은 3이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
dp() 함수를 정의합니다. idx, l_height
가 필요합니다. -
idx가 높이의 크기와 같으면 - 1이면
-
heights[idx]가 l_height와 같지 않으면 0을 반환하고 그렇지 않으면 비용[idx]
-
-
ret :=inf
-
범위 0에서 2까지의 i에 대해 수행
-
heights[idx] + i가 l_height와 같지 않으면
-
ret :=ret의 최소값, dp(idx + 1, heights[idx] + i) + 비용[idx] * i
-
-
-
리턴 렛
-
기본 메서드에서 dp(0, null)
를 반환합니다.
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
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)) 입력
[3, 2, 2], [2, 5, 3]
출력
3