Skip to content

Latest commit

 

History

History
197 lines (161 loc) · 5.31 KB

README_EN.md

File metadata and controls

197 lines (161 loc) · 5.31 KB
Raw
comments difficulty edit_url rating source tags
true
Hard
2157
Weekly Contest 286 Q4
Array
Dynamic Programming
Prefix Sum

2218. Maximum Value of K Coins From Piles

中文文档

Description

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

Solution 1

Python3

class Solution:
    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:
        presum = [list(accumulate(p, initial=0)) for p in piles]
        n = len(piles)
        dp = [[0] * (k + 1) for _ in range(n + 1)]
        for i, s in enumerate(presum, 1):
            for j in range(k + 1):
                for idx, v in enumerate(s):
                    if j >= idx:
                        dp[i][j] = max(dp[i][j], dp[i - 1][j - idx] + v)
        return dp[-1][-1]

Java

class Solution {
    public int maxValueOfCoins(List<List<Integer>> piles, int k) {
        int n = piles.size();
        List<int[]> presum = new ArrayList<>();
        for (List<Integer> p : piles) {
            int m = p.size();
            int[] s = new int[m + 1];
            for (int i = 0; i < m; ++i) {
                s[i + 1] = s[i] + p.get(i);
            }
            presum.add(s);
        }
        int[] dp = new int[k + 1];
        for (int[] s : presum) {
            for (int j = k; j >= 0; --j) {
                for (int idx = 0; idx < s.length; ++idx) {
                    if (j >= idx) {
                        dp[j] = Math.max(dp[j], dp[j - idx] + s[idx]);
                    }
                }
            }
        }
        return dp[k];
    }
}

C++

class Solution {
public:
    int maxValueOfCoins(vector<vector<int>>& piles, int k) {
        vector<vector<int>> presum;
        for (auto& p : piles) {
            int m = p.size();
            vector<int> s(m + 1);
            for (int i = 0; i < m; ++i) s[i + 1] = s[i] + p[i];
            presum.push_back(s);
        }
        vector<int> dp(k + 1);
        for (auto& s : presum) {
            for (int j = k; ~j; --j) {
                for (int idx = 0; idx < s.size(); ++idx) {
                    if (j >= idx) dp[j] = max(dp[j], dp[j - idx] + s[idx]);
                }
            }
        }
        return dp[k];
    }
};

Go

func maxValueOfCoins(piles [][]int, k int) int {
	var presum [][]int
	for _, p := range piles {
		m := len(p)
		s := make([]int, m+1)
		for i, v := range p {
			s[i+1] = s[i] + v
		}
		presum = append(presum, s)
	}
	dp := make([]int, k+1)
	for _, s := range presum {
		for j := k; j >= 0; j-- {
			for idx, v := range s {
				if j >= idx {
					dp[j] = max(dp[j], dp[j-idx]+v)
				}
			}
		}
	}
	return dp[k]
}

Solution 2

Python3

class Solution:
    def maxValueOfCoins(self, piles: List[List[int]], k: int) -> int:
        presum = [list(accumulate(p, initial=0)) for p in piles]
        dp = [0] * (k + 1)
        for s in presum:
            for j in range(k, -1, -1):
                for idx, v in enumerate(s):
                    if j >= idx:
                        dp[j] = max(dp[j], dp[j - idx] + v)
        return dp[-1]