Python에서 돌을 병합하는 최소 비용을 찾는 프로그램

<시간/>

N개의 돌 더미가 일렬로 배열되어 있다고 가정합니다. 여기서 i번째 더미에는 돌[i]개의 돌이 있습니다. 이동은 K개의 연속된 더미를 하나의 더미로 병합하는 것으로 구성되며, 이제 이 이동의 비용은 이 K개의 더미에 있는 돌의 총 수와 같습니다. 우리는 모든 돌 더미를 하나의 더미로 병합하는 최소 비용을 찾아야 합니다. 그런 솔루션이 없으면 -1을 반환합니다.

따라서 입력이 nums =[3,2,4,1], K =2와 같으면 출력은 처음에 [3, 2, 4, 1]이 있기 때문에 20이 됩니다. 그런 다음 [3, 2]를 비용 5와 병합하면 [5, 4, 1]이 됩니다. 그 후 [4, 1]을 비용 5로 병합하고 [5, 5]를 얻습니다. 그런 다음 [5, 5]를 비용 10과 병합하면 [10]이 됩니다. 따라서 총 비용은 20이었고 이것이 최소 비용입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n :=숫자 크기
(n-1) 모드(K-1)가 0이 아니면
- 반환 -1
dp :=하나의 n x n 배열 및 0으로 채우기
sums :=n 크기의 배열(n+1)이고 0으로 채움
범위 1에서 n까지의 i에 대해 수행
- 합계[i] :=합계[i-1]+숫자[i-1]
K ~ n 범위의 길이에 대해 수행
- 0에서 n-길이 범위에 있는 i에 대해 수행
  - j :=i+길이-1
  - dp[i, j] :=무한대
  - 범위 i에서 j-1까지의 t에 대해 K-1씩 각 단계에서 업데이트합니다.
    - dp[i][j] =dp[i, j]의 최소값 및 (dp[i, t] + dp[t+1, j])
  - (j-i) mod (K-1)가 0과 같으면
    - dp[i, j] :=dp[i, j] + 합계[j+1]-합[i]
반환 dp[0, n-1]

예시

더 나은 이해를 위해 다음 구현을 살펴보겠습니다.

import heapq
def solve(nums, K):
   n = len(nums)
   if (n-1)%(K-1) != 0:
      return -1
   dp = [[0]*n for _ in range(n)]
   sums = [0]*(n+1)
   for i in range(1,n+1):
      sums[i] = sums[i-1]+nums[i-1]
   for length in range(K,n+1):
      for i in range(n-length+1):
         j = i+length-1
         dp[i][j] = float('inf')
         for t in range(i,j,K-1):
            dp[i][j] = min(dp[i][j], dp[i][t]+dp[t+1][j])
         if (j-i)%(K-1)==0:
            dp[i][j] += sums[j+1]-sums[i]
   return dp[0][n-1]

nums = [3,2,4,1]
K = 2
print(solve(nums, K))

입력

[3,2,4,1], 2