길이가 같은 숫자 nums0과 nums1의 두 목록과 거리로 d, 비용으로 c가 있는 다른 두 값이 있다고 가정합니다. nums0 또는 nums1의 인덱스 0에서 시작하여 두 목록의 최종 인덱스로 끝내고자 하는 경우. 이제 각 라운드에서 비용 비용을 위해 다른 목록으로 전환하도록 선택할 수 있습니다. 그러면 인덱스에 도달하는 데 드는 c 비용이 해당 지점의 값인 곳에서 최대 d 거리만큼 앞으로 이동할 수 있습니다. 따라서 작업을 완료하는 데 가능한 최소 총 비용을 찾아야 합니다.
따라서 입력이 nums0 =[2, 3, 10, 10, 6] nums1 =[10, 10, 4, 5, 100] d =2 c =3과 같으면 출력은 18이 됩니다. 2에서 시작한 다음 두 번째 목록으로 4로 전환하고 다시 첫 번째 목록으로 다시 6으로 전환합니다. 따라서 비용 2 + 4 + 6 =12 및 비용 3으로 두 번 전환하여 총합은 18이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- switch :=nums0의 경우 키 0, nums1의 경우 키 1인 맵
- search() 함수를 정의합니다. idx, nums 가 필요합니다.
- idx>=스위치의 크기[nums]이면
- 반환 정보
- idx가 switch[nums] - 1의 크기와 같으면
- 리턴 스위치[num, -1]
- c :=정보
- 1에서 dist + 1 사이의 i에 대해
- c :=c 및 switch[nums, idx] + search(idx + i, nums)의 최소값
- c :=c 및 switch[nums, idx] + cost + search(idx + i, invert of nums)의 최소값
- 반환 c
- 메인 메소드에서 다음을 수행하십시오 -
- search(0, 0) 및 search(0, 1)의 최소값을 반환
예제(파이썬)
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
class Solution:
def solve(self, nums0, nums1, dist, cost):
switch = {0: nums0, 1: nums1}
def search(idx, nums):
if idx >= len(switch[nums]):
return float("inf")
if idx == len(switch[nums]) - 1:
return switch[nums][-1]
c = float("inf")
for i in range(1, dist + 1):
c = min(c, switch[nums][idx] + search(idx + i, nums))
c = min(c, switch[nums][idx] + cost + search(idx + i, int(not nums)))
return c
return min(search(0, 0), search(0, 1))
ob = Solution()
nums0 = [2, 3, 10, 10, 6]
nums1 = [10, 10, 4, 5, 100]
d = 2
c = 3
print(ob.solve(nums0, nums1, d, c)) 입력
[2, 3, 10, 10, 6],[10, 10, 4, 5, 100], 2, 3
출력
18