leetcode-go/medium/638.shopping-offers.go

func shoppingOffers(price []int, special [][]int, needs []int) int {
	var need [6]int
	copy(need[:], needs)
	m := make(map[[6]int]int)
	return buy(price, special, need, m) // DFS
}

func buy(price []int, special [][]int, need [6]int, m map[[6]int]int) int {
	if v, ok := m[need]; ok {
		return v
	}
	res := 0
	for i := range price {
		res += need[i] * price[i]
	} // The price without special offer
	for _, s := range special {
		var n [6]int
		copy(n[:], need[:])
		i := 0
		for ; i < len(price); i++ {
			n[i] -= s[i]
			if n[i] < 0 {
				break
			}
		}
		if i == len(price) {
			res = minInt(res, s[i]+buy(price, special, n, m))
		}
	}
	m[need] = res
	return res
}

func minInt(x, y int) int {
	if x < y {
		return x
	}
	return y
}