最低票价

题目描述

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
}

思路

题解答案，记忆搜索，每次进行三次的搜索，分别搜索三个价格；if pDay > 365|| pDay >= len(pMem) 做了优化。