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

dp真的好難

dp真的難 我刷了一陣子還是沒啥進步