双参数动态规划求助：餐厅优惠券最优方案调试

DevOps 小满

2026-7-29

问题描述

餐厅折扣规则：单次消费超过100美元可获得1张免费午餐优惠券。给定未来N天的午餐价格列表（示例输入：

），价格范围为0≤price≤300。需求是计算午餐的最小总成本，以及使用优惠券的日期。

本人无法正确处理边缘情况，不确定初始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
}

扩展后的实现代码

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
}

测试失败用例

输入数据：

预期输出：

说明：10天每天消费101美元，每消费一次得1张优惠券，最优策略是用优惠券抵消偶数天的费用，总成本为5*101=505，剩余5张优惠券，使用优惠券的日期为第2、4、6、8、10天。

修正后的稳定DP实现

package main

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

func main() {
	file, _ := os.ReadFile("input.txt")
	lines := strings.Split(string(file), "\n")

	var p []int
	for _, line := range lines {
		price, err := strconv.Atoi(line)
		if err != nil {
			continue
		}
		p = append(p, price)
	}
	n := len(p)
	if n == 0 {
		fmt.Println(0)
		fmt.Println("0 0")
		return
	}

	// dp[i][j]：处理完前i天，剩余j张优惠券的最小总成本
	maxCoupons := n
	dp := make([][]int, n+1)
	for i := range dp {
		dp[i] = make([]int, maxCoupons+1)
		for j := range dp[i] {
			dp[i][j] = math.MaxInt32
		}
	}
	dp[0][0] = 0 // 初始状态：0天，0优惠券，成本0

	for i := 1; i <= n; i++ {
		price := p[i-1]
		for j := 0; j <= maxCoupons; j++ {
			// 情况1：付费当天的午餐
			if dp[i-1][j] != math.MaxInt32 {
				newCost := dp[i-1][j] + price
				newJ := j
				if price > 100 {
					newJ += 1
					if newJ > maxCoupons {
						newJ = maxCoupons
					}
				}
				if newCost < dp[i][newJ] {
					dp[i][newJ] = newCost
				}
			}

			// 情况2：使用优惠券抵消当天的午餐（仅当有优惠券时）
			if j > 0 && dp[i-1][j-1] != math.MaxInt32 {
				if dp[i-1][j-1] < dp[i][j] {
					dp[i][j] = dp[i-1][j-1]
				}
			}
		}
	}

	// 找到最小总成本，以及对应的剩余优惠券数量
	minTotal := math.MaxInt32
	remainingCoupons := 0
	for j := 0; j <= maxCoupons; j++ {
		if dp[n][j] < minTotal {
			minTotal = dp[n][j]
			remainingCoupons = j
		}
	}

	// 回溯找到使用优惠券的日期
	couponDays := []int{}
	currentJ := remainingCoupons
	currentCost := minTotal

	for i := n; i >= 1; i-- {
		price := p[i-1]
		// 检查是否是使用优惠券的情况
		if currentJ > 0 && dp[i-1][currentJ-1] == currentCost {
			couponDays = append(couponDays, i)
			currentJ--
			continue
		}

		// 检查是否是付费的情况
		prevJ := currentJ
		if price > 100 {
			prevJ = currentJ - 1
			if prevJ < 0 {
				prevJ = 0
			}
		}
		if prevJ >= 0 && dp[i-1][prevJ] != math.MaxInt32 && dp[i-1][prevJ]+price == currentCost {
			currentCost -= price
			currentJ = prevJ
			continue
		}
	}

	// 排序日期
	sort.Ints(couponDays)

	// 输出结果
	fmt.Println(minTotal)
	fmt.Printf("%d %d\n", remainingCoupons, len(couponDays))
	for _, day := range couponDays {
		fmt.Println(day)
	}
}

代码说明

DP状态定义：dp[i][j]表示处理完前i天，剩余j张优惠券时的最小总成本，初始状态dp[0][0] = 0，其余状态初始化为math.MaxInt32表示不可达。
状态转移：
- 付费分支：若前i-1天剩余j张优惠券，付费当前午餐后，总成本增加当前价格；若当前价格超过100，优惠券数量加1。
- 使用优惠券分支：若前i-1天剩余j-1张优惠券，使用一张优惠券抵消当前午餐，总成本不变，剩余优惠券数量变为j。
回溯逻辑：从最后一天倒推，判断当天是使用优惠券还是付费，记录使用优惠券的日期。
边界处理：正确处理优惠券数量的上下限，避免越界；使用math.MaxInt32标记不可达状态，避免错误的最小值计算。

内容的提问来源于stack exchange，提问作者Павел Вайсберг