Go 具有两个参数的动态规划：天数和优惠券

有一家咖啡馆实行以下折扣制度:每购买more美元以上more美元，买家就会收到一张优惠券，有权获得一顿免费午餐. 您有future N天的价目表，如下所示:

5
35
40
101
59
63

你决定每天吃饭，所以找出午餐可能的最低总成本，以及你应该使用优惠券的天数. 请帮助稳定DP履行.我不确定初始DP表是否适合该任务，因此我无法正确处理边缘情况:

func main() {
    file, _ := os.ReadFile("input.txt")

    lines := strings.Split(string(file), "\n")

    p := make([]int, 0, len(lines))

    for i := 0; i < len(lines); i++ {
        price, err := strconv.Atoi(lines[i])

        if err != nil {
            continue
        }

        p = append(p, price)
    }

    dp := make([][]int, len(p)+1)
    dp[0] = make([]int, len(dp))
    
    // zero day row
    for i := 1; i < len(dp); i++ {
        // no coupons on the first day visit
        dp[0][i] = math.MaxInt32
    }
    
    // 1...N days
    for i := 1; i < len(dp); i++ {
        dp[i] = make([]int, len(p))
    }

    for i := 1; i <= len(p); i++ {
        for j := 0; j < len(p); j++ {
            if p[i-1] <= 100 {
                dp[i][j] = Min(dp[i-1][j]+p[i-1], dp[i-1][j+1])
            }

            dp[i][j] = Min(dp[i-1][j-1]+p[i-1], dp[i-1][j+1])
        }
    }

    fmt.Println(dp)
}

func Min(i, j int) int {
    if i <= j {
        return i
    }

    return j
}

谢谢.

UPD.看似达到最佳效果但未被3RT方测试系统接受的扩展解决方案:

package main

import (
    "fmt"
    "math"
    "os"
    "sort"
    "strconv"
    "strings"
)

func main() {
    file, _ := os.ReadFile("input.txt")

    lines := strings.Split(string(file), "\n")

    p := make([]int, 0, len(lines))

    for i := 1; i < len(lines); i++ {
        price, err := strconv.Atoi(lines[i])

        if err != nil {
            continue
        }

        p = append(p, price)
    }

    l := len(p)

    dp := make([][]int, l+1)
    dp[0] = make([]int, len(dp))

    for i := 1; i < len(dp); i++ {
        dp[0][i] = math.MaxInt32
    }

    for i := 1; i < len(dp); i++ {
        dp[i] = make([]int, l+1)
    }

    // fill dp
    for i := 1; i <= l; i++ {
        for j := 0; j <= l; j++ {
            if p[i-1] <= 100 {
                if j == l {
                    dp[i][j] = MinOrZero(dp[i-1][j]+p[i-1], dp[i-1][j])
                    continue
                }

                dp[i][j] = MinOrZero(dp[i-1][j]+p[i-1], dp[i-1][j+1])
                continue
            }

            if j == 0 {
                dp[i][j] = MinOrZero(math.MaxInt32, dp[i-1][j+1])
                continue
            }

            if j == l {
                dp[i][j] = MinOrZero(dp[i-1][j-1]+p[i-1], dp[i-1][j])
                continue
            }

            dp[i][j] = MinOrZero(dp[i-1][j-1]+p[i-1], dp[i-1][j+1])
        }
    }
    
    // coupons left
    coupons := 0
    min := math.MaxInt

    for j := l; j >= 0; j-- {
        sum := dp[l][j]

        if sum < min {
            min = sum
            coupons = j
        }
    }

    couponDays := make([]int, 0)
    j := coupons
    sum := min

    for i := l; i > 0; i-- {
        jl := j - 1
        js := j
        jr := j + 1

        if jr < l && dp[i-1][jr] == sum {
            couponDays = append(couponDays, i)
            j++
            continue
        }

        if dp[i-1][js] == sum {
            sum = dp[i-1][js]
            continue
        }

        if jl >= 0 && dp[i-1][jl] == sum-p[i-1] {
            sum = dp[i-1][jl]
            j--
            continue
        }

        sum -= p[i-1]
    }

    sort.Ints(couponDays)

    fmt.Println(min)
    fmt.Println(fmt.Sprintf("%d %d", coupons, len(couponDays)))
    for _, day := range couponDays {
        fmt.Println(day)
    }
}

func Min(i, j int) int {
    if i <= j {
        return i
    }

    return j
}

func MinOrZero(i, j int) int {
    var result int

    if i <= j {
        result = i
    } else {
        result = j
    }

    if result >= 0 {
        return result
    }

    return 0
}