There are N piles of stones arranged in a row. The i-th pile has stones[i] stones.
A move consists of merging exactly K consecutive piles into one pile, and the cost of this move is equal to the total number of stones in these K piles.
Find the minimum cost to merge all piles of stones into one pile. If it is impossible, return -1.
Example 1:
Input: stones = [3,2,4,1], K = 2
Output: 20
Explanation:
We start with [3, 2, 4, 1].
We merge [3, 2] for a cost of 5, and we are left with [5, 4, 1].
We merge [4, 1] for a cost of 5, and we are left with [5, 5].
We merge [5, 5] for a cost of 10, and we are left with [10].
The total cost was 20, and this is the minimum possible.
Example 2:
Input: stones = [3,2,4,1], K = 3
Output: -1
Explanation: After any merge operation, there are 2 piles left, and we can't merge anymore. So the task is impossible.
Example 3:
Input: stones = [3,5,1,2,6], K = 3
Output: 25
Explanation:
We start with [3, 5, 1, 2, 6].
We merge [5, 1, 2] for a cost of 8, and we are left with [3, 8, 6].
We merge [3, 8, 6] for a cost of 17, and we are left with [17].
The total cost was 25, and this is the minimum possible.
Note:
1 <= stones.length <= 30
2 <= K <= 30
1 <= stones[i] <= 100
Solution: DP
dp[i][j][k] := min cost to merge subarray i ~ j into k piles Init: dp[i][j][k] = 0 if i==j and k == 1 else inf ans: dp[0][n-1][1] transition: 1. dp[i][j][k] = min{dp[i][m][1] + dp[m+1][j][k-1]} for all i <= m < j 2. dp[i][j][1] = dp[i][j][K] + sum(A[i]~A[j])
Time complexity: O(n^3) Space complexity: O(n^2*K)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// Running time: 12 ms, 12.1 MB
classSolution{
public:
intmergeStones(vector<int>& stones, int K) {
const int n = stones.size();
if((n-1)%(K-1))return-1;
constintkInf=1e9;
vector<int>sums(n+1);
for(inti=0;i<stones.size();++i)
sums[i+1]=sums[i]+stones[i];
// dp[i][j][k] := min cost to merge subarray i~j into k piles.
std::function<int(int,int,int)>dp=[&stones, &sums, &cache, kInf, n, K, &dp](int i, int j, int k) {
if ((j - i + 1 - k) % (K - 1)) return kInf;
if(i==j)returnk==1?0:kInf;
if(cache[i][j][k]!=INT_MAX)returncache[i][j][k];
if(k==1)
returncache[i][j][k]=dp(i,j,K)+sums[j+1]-sums[i];
intans=kInf;
for(intm=i;m<j;m+=K-1){
intl=dp(i,m,1);
if(l>=ans)continue;
intr=dp(m+1,j,k-1);
if(r>=ans)continue;
ans=min(ans,l+r);
}
returncache[i][j][k]=ans;
};
returndp(0,n-1,1);
}
};
Solution 2: DP
dp[l][i] := min cost to merge [i, i + l) into as less piles as possible. Number of merges will be (l-1) / (K – 1) and Transition: dp[l][i] = min(dp[m][i] + dp[l – m][i + m]) for 1 <= m < l if ((l – 1) % (K – 1) == 0) [i, i + l) can be merged into 1 pile, dp[l][i] += sum(A[i:i+l])
Time complexity: O(n^3 / k) Space complexity: O(n^2)
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// Author: Huahua 4ms, 9.6 MB
classSolution{
public:
intmergeStones(vector<int>& stones, int K) {
const int n = stones.size();
if((n-1)%(K-1))return-1;
vector<int>sums(n+1);
for(inti=0;i<stones.size();++i)
sums[i+1]=sums[i]+stones[i];
constintkInf=1e9;
// dp[i][j] := min cost to merge subarray A[i] ~ A[j] into (j-i)%(K-1) + 1 piles
vector<vector<int>>dp(n,vector<int>(n,kInf));
for(inti=0;i<n;++i)dp[i][i]=0;
for(intl=2;l<=n;++l)// subproblem length
for(inti=0;i<=n-l;++i){// start
intj=i+l-1;
for(intm=i;m<j;m+=K-1)// split point
dp[i][j]=min(dp[i][j],dp[i][m]+dp[m+1][j]);
// If the current length can be merged into 1 pile
In a country popular for train travel, you have planned some train travelling one year in advance. The days of the year that you will travel is given as an array days. Each day is an integer from 1 to 365.
Train tickets are sold in 3 different ways:
a 1-day pass is sold for costs[0] dollars;
a 7-day pass is sold for costs[1] dollars;
a 30-day pass is sold for costs[2] dollars.
The passes allow that many days of consecutive travel. For example, if we get a 7-day pass on day 2, then we can travel for 7 days: day 2, 3, 4, 5, 6, 7, and 8.
Return the minimum number of dollars you need to travel every day in the given list of days.
Example 1:
Input: days = [1,4,6,7,8,20], costs = [2,7,15]
Output: 11
Explanation:
For example, here is one way to buy passes that lets you travel your travel plan:
On day 1, you bought a 1-day pass for costs[0] = $2, which covered day 1.
On day 3, you bought a 7-day pass for costs[1] = $7, which covered days 3, 4, ..., 9.
On day 20, you bought a 1-day pass for costs[0] = $2, which covered day 20.
In total you spent $11 and covered all the days of your travel.
Example 2:
Input: days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]
Output: 17
Explanation:
For example, here is one way to buy passes that lets you travel your travel plan:
On day 1, you bought a 30-day pass for costs[2] = $15 which covered days 1, 2, ..., 30.
On day 31, you bought a 1-day pass for costs[0] = $2 which covered day 31.
In total you spent $17 and covered all the days of your travel.
Note:
1 <= days.length <= 365
1 <= days[i] <= 365
days is in strictly increasing order.
costs.length == 3
1 <= costs[i] <= 1000
Solution: DP
dp[i] := min cost to cover the i-th day dp[0] = 0 dp[i] = min(dp[i – 1] + costs[0], dp[i – 7] + costs[1], dp[i – 30] + costs[2])
dp[i][j] := max length of all 1 sequence ends with col j, at the i-th row. transition: dp[i][j] = 0 if matrix[i][j] == ‘0’ = dp[i][j-1] + 1 if matrix[i][j] == ‘1’