# Leetcode 2218. Maximum Value of K Coins From Piles
###### tags: `leetcode` `daily` `DP`

[題目連結](https://leetcode.com/problems/maximum-value-of-k-coins-from-piles/)

# Method DP
**Basic sitituation**
:::warning
if we have two piles, we need to get two coins,
> case 1: first pile, two coins.
>
> case 2: first pile, one coin, second pile, one coin.
>
> case 3: second pile, two coins.
>
:::

**sub problem defintion**
:::warning
prefix Piles using `i` coins, the next piles we need get `k - i` coins.
:::

:::info
:bulb: **作法講解**:
we can define `dp[i] = x`,
it means using ith coins, the maximum value is `x`.

DP iteration:
Prefix piles, we get i coin.
Current pile, we get j coin, the sum of coin is `sum[j]`.
`dp[i+j] = max(dp[i+j], dp[i] + sum[j])`

the maximum value of get exactly k coin is `dp[k]`
:::

TC: O(N*K) SC: O(K)

class Solution {
public:
    int maxValueOfCoins(vector<vector<int>>& piles, int k) {
        vector<int> dp(k+1, 0);

        for(vector<int> &v : piles) {
            vector<int> next = dp;
            int sum = 0;
            for(int i = 0 ; i < v.size(); i++) {
                sum += v[i];
                for(int j = 0 ; i+j < k ; j++) {
                    next[i+j+1] = max(next[i+j+1], dp[j] + sum);
                }
            }
            dp = next;
        }
        return dp[k];
    }
};