README.md

2218. Maximum Value of K Coins From Piles

There are n piles of coins on a table. Each pile consists of a positive number of coins of assorted denominations.

In one move, you can choose any coin on top of any pile, remove it, and add it to your wallet.

Given a list piles, where piles[i] is a list of integers denoting the composition of the ith pile from top to bottom, and a positive integer k, return the maximum total value of coins you can have in your wallet if you choose exactly k coins optimally.

Example 1:

Input: piles = [[1,100,3],[7,8,9]], k = 2
Output: 101
Explanation:
The above diagram shows the different ways we can choose k coins.
The maximum total we can obtain is 101.

Example 2:

Input: piles = [[100],[100],[100],[100],[100],[100],[1,1,1,1,1,1,700]], k = 7
Output: 706
Explanation:
The maximum total can be obtained if we choose all coins from the last pile.

Constraints:

• n == piles.length
• 1 <= n <= 1000
• 1 <= piles[i][j] <= 105
• 1 <= k <= sum(piles[i].length) <= 2000

Solutions (Rust)

1. Solution

impl Solution {
    pub fn max_value_of_coins(piles: Vec<Vec<i32>>, k: i32) -> i32 {
        let k = k as usize;
        let n = piles.len();
        let mut dp = vec![vec![0; k + 1]; n + 1];

        for i in 0..n {
            for j in 0..=k {
                let mut total = 0;

                dp[i + 1][j] = dp[i + 1][j].max(dp[i][j]);
                for m in 0..piles[i].len().min(k - j) {
                    total += piles[i][m];
                    dp[i + 1][j + m + 1] = dp[i + 1][j + m + 1].max(total + dp[i][j]);
                }
            }
        }

        dp[n][k]
    }
}