Dynamic programming with two parameters: days and coupons

There is a cafe that has the following discount system: for each purchase of more than $100, the buyer receives a coupon that gives the right to one free lunch.
You have a price list for the next N days like:

5
35
40
101
59
63

The price limitation: 0 ≤ price ≤ 300

Find the minimum possible total cost of lunches and the numbers of days on which you should use the coupons.

Please help to stabilize DP fulfilling. I am not sure the initial DP table is suitable for the task so I can not handle edge cases correctly:

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
}

Thank you.

Upd. Extended solution which seems to achieve the best results but is unaccepted by 3rt party testing system:

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
}

Input data test fails on. And the answer should be.

To be able to return the days on which the coupons were used you need to keep track of the best path and then you can go backwards at the end.

You have to be very careful when tickets are used or gained because it shifts the position in the dp array. Some positions can stay undefined. E.g. if you get a ticket on the first day then the cell corresponding to 0 tickets stays undefined, because the costs for the day are put at 1 tickets (and if the price is above 100 the next day we end up with 0 or 2 tickets, but not with 1). If that jumping up and down is done correctly it should work.

<!-- begin snippet: js hide: false console: true babel: false -->

<!-- language: lang-js -->

function solve(prices) {
const dp = [[]], n = prices.length
let tickets = prices[0] > 100 ? 1 : 0
dp[0][tickets] = {cost: prices[0]}
for (let i = 1; i < n; i++) {
dp.push([])
let t = prices[i] > 100 ? 1 : 0
// not using tickets
for (let j = 0; j <= tickets; j++)
if (dp[i - 1][j])
dp[i][j + t] = {cost: dp[i - 1][j].cost + prices[i], prev: j}
// using tickets
for (let j = 1; j <= tickets; j++)
if (dp[i - 1][j] && (!dp[i][j - 1] || dp[i][j - 1].cost > dp[i - 1][j].cost))
dp[i][j - 1] = {cost: dp[i - 1][j].cost, prev: j}
tickets += t
}
// min has to be at 0 or 1 ticket
let idx = dp[n - 1][0] && (!dp[n - 1][1] || dp[n - 1][0].cost <= dp[n - 1][1].cost) ? 0 : 1
console.log('costs: ' + dp[n - 1][idx].cost)
const days = []
for (let day = n - 1; day > 0; day--) {
if (dp[day][idx].prev > idx)
days.unshift(day)
idx = dp[day][idx].prev
}
console.log('days: ' + days)
}
solve([88,55,101,77,44,130,160,22,55,97,101,2,88])

<!-- end snippet -->