|
| 1 | +#!/usr/bin/python3 |
| 2 | +""" |
| 3 | +There are N piles of stones arranged in a row. The i-th pile has stones[i] |
| 4 | +stones. |
| 5 | +
|
| 6 | +A move consists of merging exactly K consecutive piles into one pile, and the |
| 7 | +cost of this move is equal to the total number of stones in these K piles. |
| 8 | +
|
| 9 | +Find the minimum cost to merge all piles of stones into one pile. If it is |
| 10 | +impossible, return -1. |
| 11 | +
|
| 12 | +
|
| 13 | +
|
| 14 | +Example 1: |
| 15 | +
|
| 16 | +Input: stones = [3,2,4,1], K = 2 |
| 17 | +Output: 20 |
| 18 | +Explanation: |
| 19 | +We start with [3, 2, 4, 1]. |
| 20 | +We merge [3, 2] for a cost of 5, and we are left with [5, 4, 1]. |
| 21 | +We merge [4, 1] for a cost of 5, and we are left with [5, 5]. |
| 22 | +We merge [5, 5] for a cost of 10, and we are left with [10]. |
| 23 | +The total cost was 20, and this is the minimum possible. |
| 24 | +Example 2: |
| 25 | +
|
| 26 | +Input: stones = [3,2,4,1], K = 3 |
| 27 | +Output: -1 |
| 28 | +Explanation: After any merge operation, there are 2 piles left, and we can't |
| 29 | +merge anymore. So the task is impossible. |
| 30 | +Example 3: |
| 31 | +
|
| 32 | +Input: stones = [3,5,1,2,6], K = 3 |
| 33 | +Output: 25 |
| 34 | +Explanation: |
| 35 | +We start with [3, 5, 1, 2, 6]. |
| 36 | +We merge [5, 1, 2] for a cost of 8, and we are left with [3, 8, 6]. |
| 37 | +We merge [3, 8, 6] for a cost of 17, and we are left with [17]. |
| 38 | +The total cost was 25, and this is the minimum possible. |
| 39 | +
|
| 40 | +
|
| 41 | +Note: |
| 42 | +
|
| 43 | +1 <= stones.length <= 30 |
| 44 | +2 <= K <= 30 |
| 45 | +1 <= stones[i] <= 100 |
| 46 | +""" |
| 47 | +fromtypingimportList |
| 48 | +fromfunctoolsimportlru_cache |
| 49 | + |
| 50 | + |
| 51 | +classSolution: |
| 52 | +defmergeStones(self,stones:List[int],K:int)->int: |
| 53 | +""" |
| 54 | + Mergeable? K -> 1. Reduction size (K - 1) |
| 55 | + N - (K - 1) * m = 1 |
| 56 | + mergeable: (N - 1) % (K - 1) = 0 |
| 57 | +
|
| 58 | + K consecutive |
| 59 | + every piles involves at least once |
| 60 | + Non-consecutive: priority queue merge the least first |
| 61 | + But here it is consecutive, need to search, cannot gready |
| 62 | +
|
| 63 | + * Merge the piles cost the same as merge individual ones. |
| 64 | +
|
| 65 | + Attemp 1: |
| 66 | + F[i] = cost to merge A[:i] into 1 |
| 67 | + F[i] = F[i-3] + A[i-1] + A[i-2] + A[i-3] ?? |
| 68 | +
|
| 69 | + Attemp 2: |
| 70 | + F[i][j] = cost of merge A[i:j] into 1 |
| 71 | + F[i][j] = F[i][k] + F[k][j] ?? |
| 72 | +
|
| 73 | + Answer: |
| 74 | + F[i][j][m] = cost of merge A[i:j] into m piles |
| 75 | + F[i][j][1] = F[i][j][k] + sum(stones[i:j]) # merge |
| 76 | + F[i][j][m] = min F[i][mid][1] + F[mid][j][m-1] # add |
| 77 | +
|
| 78 | + initial: |
| 79 | + F[i][i+1][1] = 0 |
| 80 | + F[i][i+1][m] = inf |
| 81 | +
|
| 82 | + since the mid goes through the middle in the i, j. |
| 83 | + Use memoization rather than dp |
| 84 | + """ |
| 85 | +N=len(stones) |
| 86 | +sums= [0] |
| 87 | +forsinstones: |
| 88 | +sums.append(sums[-1]+s) |
| 89 | + |
| 90 | +@lru_cache(None) |
| 91 | +defF(i,j,m): |
| 92 | +ifi>=jorm<1: |
| 93 | +returnfloat("inf") |
| 94 | + |
| 95 | +n=j-i |
| 96 | +if (n-m)% (K-1)!=0: |
| 97 | +returnfloat("inf") |
| 98 | + |
| 99 | +ifj==i+1: |
| 100 | +ifm==1: |
| 101 | +return0 |
| 102 | +returnfloat("inf") |
| 103 | + |
| 104 | +ifm==1: |
| 105 | +returnF(i,j,K)+sums[j]-sums[i] |
| 106 | + |
| 107 | +ret=min( |
| 108 | +F(i,mid,1)+F(mid,j,m-1) |
| 109 | +formidinrange(i+1,j,K-1) |
| 110 | + ) |
| 111 | +returnret |
| 112 | + |
| 113 | +ret=F(0,N,1) |
| 114 | +returnretifret!=float("inf")else-1 |
| 115 | + |
| 116 | + |
| 117 | +if__name__=="__main__": |
| 118 | +assertSolution().mergeStones([3,5,1,2,6],3)==25 |