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.初始化变量:定义一个数组用于记录计算过程中的最大值,长度为,初始值全为 0。
dp
k+1
2.循环遍历每个栈在中:
stack
piles
2.1.对于每个栈,从最大次数开始递减到 1:
stack
k
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.空间复杂度:
- •需要额外的数组来存储计算所需的值,长度为 k+1,即 O(k) 的额外空间。
- dp
- •因此,总的额外空间复杂度为 O(k)。
Go语言代码如下:
packagemain
import(
"fmt"
"math"
)
funcmaxValueOfCoins(piles[][]int,kint)int{
dp:=make([]int,k+1)
for_,stack:=rangepiles{
forw:=k;w>0;w--{
varsumint
fori:=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])))
}
}
}
returndp[k]
}
funcmain(){
piles:=[][]int{{1,100,3},{7,8,9}}
k:=2
result:=maxValueOfCoins(piles,k)
fmt.Println(result)
}
Python语言代码如下:
#-*-coding:utf-8-*-
defmax_value_of_coins(piles,k):
dp=[0]*(k+1)
forstackinpiles:
forwinrange(k,0,-1):
sum_val=0
foriinrange(1,min(len(stack),w)+1):
sum_val+=stack[i-1]
dp[w]=max(dp[w],sum_val+dp[w-i])
returndp[k]
defmain():
piles=[[1,100,3],[7,8,9]]
k=2
result=max_value_of_coins(piles,k)
print(result)
if__name__=="__main__":
main()
特别声明:以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布,本平台仅提供信息存储服务。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.