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