Re: [閒聊] 每日leetcode
3366. Minimum Array Sum
這題我看到有人用greedy
不過我看不懂
思路:
DP解
dp[i][j]表示能做i次op1、j次op2可以得到的最小值
就是對每個數字都去跑4種狀況
1. OP1、OP2都做
2.只做OP1
3.只做OP2
4.都不做
最後回傳dp[op1][op2]就好
golang code :
func minArraySum(nums []int, k, op1, op2 int) int {
dp := make([][]int, op1+1)
for i := 0; i <= op1; i++ {
dp[i] = make([]int, op2+1)
}
for _, x := range nums {
var y int
//op1、op2都做其實還有分先後
if (x+1)/2 >= k { //op1先做,扣比較多的情況
y = (x+1)/2 - k
} else { //op2先做,扣比較多的情況
y = (x - k + 1) / 2
}
for i := op1; i >= 0; i-- { //一定要從OP1開始不能從0開始,不然會去動到舊狀態(
dp[op1-1][...])
for j := op2; j >= 0; j-- { //一定要從OP2開始不能從0開始,不然會去動到舊狀態
(dp[...][op2-1])
dp[i][j] = dp[i][j] + x //都不做
if i > 0 { //只做OP1
dp[i][j] = min(dp[i][j], dp[i-1][j]+(x+1)/2)
}
if j > 0 && x >= k { //大於k才能做2
dp[i][j] = min(dp[i][j], dp[i][j-1]+x-k) //只做OP2
if i > 0 { //做OP1+OP2
dp[i][j] = min(dp[i][j], dp[i-1][j-1]+y)
}
}
}
}
}
return dp[op1][op2]
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.73.67.204 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1732716402.A.59C.html
→
11/27 22:07,
1年前
, 1F
11/27 22:07, 1F
推
11/27 22:11,
1年前
, 2F
11/27 22:11, 2F
討論串 (同標題文章)
完整討論串 (本文為第 1162 之 1548 篇)：