題目描述
https://leetcode-cn.com/problems/minimum-cost-for-tickets/
解
package main
func mincostTickets(days []int, costs []int) int {
if len(days) == 0 || len(costs) != 3 {
return 0
}
var mem = make([]int, days[len(days)-1]+1,366)
var dayInfo = make(map[int]struct{})
for _, v := range days {
dayInfo[v] = struct{}{}
}
return mincostTicketsMem(1, mem, costs, dayInfo)
}
func mincostTicketsMem(pDay int, pMem, pCost []int, pDayInfo map[int]struct{}) int {
if pDay > 365|| pDay >= len(pMem) {
return 0
}
if pMem[pDay] != 0 {
return pMem[pDay]
}
if _, ok := pDayInfo[pDay]; ok {
pMem[pDay] = Min(mincostTicketsMem(pDay+1, pMem, pCost, pDayInfo)+pCost[0], mincostTicketsMem(pDay+7, pMem, pCost, pDayInfo)+pCost[1], mincostTicketsMem(pDay+30, pMem, pCost, pDayInfo)+pCost[2])
} else {
pMem[pDay] = mincostTicketsMem(pDay+1, pMem, pCost, pDayInfo)
}
return pMem[pDay]
}
func Min(i, j, k int) int {
if i < j {
if i < k {
return i
}
return k
}
if j < k {
return j
}
return k
}
思路
題解答案院尔，記憶搜索蜻展，每次進(jìn)行三次的搜索，分別搜索三個價格邀摆；if pDay > 365|| pDay >= len(pMem) 做了優(yōu)化纵顾。
結(jié)果
