2024-03-23：用 go 语言，一张桌子上总共有 n 个硬币栈。每个栈有正整数个带面值的硬币，每一次操作中，你可以从任意一个栈的顶部取出 1 个硬币，从栈中移除它，并放入你的钱包里。

作者：福大大架构师每日一题

2024-03-23
北京
本文字数：1121 字
阅读完需：约 4 分钟

2024-03-23：用 go 语言，一张桌子上总共有 n 个硬币栈。每个栈有正整数个带面值的硬币，

每一次操作中，你可以从任意一个栈的顶部取出 1 个硬币，从栈中移除它，并放入你的钱包里。

给你一个列表 piles ，其中 piles[i] 是一个整数数组，

分别表示第 i 个栈里从顶到底的硬币面值。同时给你一个正整数 k。

请你返回在恰好进行 k 次操作的前提下，你钱包里硬币面值之和最大为多少？

输入：piles = [[1,100,3],[7,8,9]], k = 2。

输出：101。

答案 2024-03-23：

来自左程云。

灵捷3.5

大体过程如下：

1.初始化变量：定义一个 dp 数组用于记录计算过程中的最大值，长度为 k+1，初始值全为 0。

2.循环遍历每个栈 stack 在 piles 中：

2.1.对于每个栈 stack，从最大次数 k 开始递减到 1：

2.1.1.定义变量 sum 用于记录当前栈取出的硬币总和。

2.1.2.遍历从 1 到 min(栈的长度, 次数) 的取数次数 i：

2.1.2.1.计算当前次数下取的硬币总和并更新到 sum 中。

2.1.2.2.更新 dp[次数] 为当前 dp[次数] 与取出当前硬币后的最大值（sum + dp[次数-i]）的较大者。

3.返回 dp[k]，即完成 k 次操作后的最大硬币面值之和。

4.时间复杂度：

遍历每个栈需要 O(n) 的时间，n 为栈的数量。
每个栈内部的计算复杂度为 O(k * m)，其中 m 为栈内硬币的数量。
因此，总的时间复杂度为 O(nkm)。

5.空间复杂度：

需要额外的 dp 数组来存储计算所需的值，长度为 k+1，即 O(k) 的额外空间。
因此，总的额外空间复杂度为 O(k)。

Go 语言代码如下：

package main
import (  "fmt"  "math")
func maxValueOfCoins(piles [][]int, k int) int {  dp := make([]int, k+1)
  for _, stack := range piles {    for w := k; w > 0; w-- {      var sum int      for i := 1; i <= int(math.Min(float64(len(stack)), float64(w))); i++ {        sum += stack[i-1]        dp[w] = int(math.Max(float64(dp[w]), float64(sum+dp[w-i])))      }    }  }
  return dp[k]}
func main() {  piles := [][]int{{1, 100, 3}, {7, 8, 9}}  k := 2
  result := maxValueOfCoins(piles, k)  fmt.Println(result)}

复制代码

Python 语言代码如下：

# -*-coding:utf-8-*-
def max_value_of_coins(piles, k):    dp = [0] * (k+1)
    for stack in piles:        for w in range(k, 0, -1):            sum_val = 0            for i in range(1, min(len(stack), w)+1):                sum_val += stack[i-1]                dp[w] = max(dp[w], sum_val + dp[w - i])
    return dp[k]
def main():    piles = [[1, 100, 3], [7, 8, 9]]    k = 2    result = max_value_of_coins(piles, k)    print(result)
if __name__ == "__main__":    main()