https://leetcode.com/problems/maximum-value-of-k-coins-from-piles/
這題是稍微複雜一點的 dynamic programming 的問題。
定義 dp[i][j] 爲 「在前 i 堆裡面選 j 次中最多硬幣的數量」。
對於 dp[i][j] ，
若是我在第 i 堆選 0 次，那麼我得到的硬幣數量是 dp[i - 1][j]
若是我在第 i 堆選 1 次，那麼我得到的硬幣數量是 dp[i - 1][j - 1] + piles[i][0]
若是我在第 i 堆選 2 次，那麼我得到的硬幣數量是 dp[i - 1][j - 2] + piles[i][0] + piles[i][1]
…
若是我在第 i 堆選 k 次，那麼我得到的硬幣數量是 dp[i - 1][j - k] + piles[i][0] + piles[i][1] + ... + piles[i][k]
…
若是我在第 i 堆選 j 次，那麼我得到的硬幣數量是 dp[i - 1][0] + piles[i][0] + piles[i][1] + ... + piles[i][j]
但是這邊要注意 k <= min(piles[i].size(), j)，因爲第 i 堆最多只能選 piles[i].size() 那麼多次。
也就是說 dp[i][j] = max(dp[i - 1][j - k] + (piles[i][k])) for k = 0 to min(piles[i].size(), j)。
那接下來就直接跑過 i, j 然後把上面的關係式套進去就好了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| int maxValueOfCoins(vector<vector<int>>& piles, int K) {
int n = piles.size();
vector<vector<int>> dp(n + 1, vector<int> (K + 1, 0));
for (int i = 1; i <= n; i++){
int size = piles[i - 1].size(); // 第 i 堆對應的 index 是 i - 1
int prefix = 0;
for (int j = 1; j <= K; j++){
int prefix = 0;
dp[i][j] = dp[i - 1][j];
for (int k = 1; k <= size && k <= j; k++){
prefix += piles[i - 1][k - 1];
dp[i][j] = max(dp[i][j], prefix + dp[i - 1][j - k]);
}
}
}
return dp[n][K];
}
|
一樣也可以寫成 top down 的做法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| int maxValueOfCoins(vector<vector<int>>& piles, int K) {
int n = piles.size();
vector<vector<int>> memo(n + 1, vector<int> (K + 1, 0));
return dp(memo, piles, n, K);
}
int dp(vector<vector<int>> &memo, vector<vector<int>>& piles, int i, int j){
if (i == 0 || j == 0){
return 0;
}
if (memo[i][j] > 0){
return memo[i][j];
}
int best = dp(memo, piles, i - 1, j);
int prefix = 0;
int size = piles[i - 1].size();
for (int k = 1; k <= j && k <= size; k++){
prefix += piles[i - 1][k - 1];
best = max(best, dp(memo, piles, i - 1, j - k) + prefix);
}
memo[i][j] = best;
return best;
}
|
time complexity: O( K * m ) where m = sum(piles[i].size())
當計算 dp[i][j] 時，for loop 要跑 piles[i - 1].size() 次，所以計算 dp[1][j] 到 dp[n][j] 要跑 sum(piles[i].size()) 次。而 j 要從 1 跑到 K，所以總共要跑 K * sum(piles[i].size()) 次。
space complextiy: O( n * K )