leetcode | go | 第983题 | 最低票价

最低票价

go

解决思路

1. n 为 days[len(days)-1]，dp 为长为 n+1 的数组，set 为需要购票的天数的集合
2. 遍历 days（当前的天数为 day），将 day 加入 set。边界条件为 dp[days[0]] 为 cost[0]、cost[1]、cost[2] 中的最小值
3. i 从 days[0]+1 遍历到 n。如果 set[i]（需要购票），dp[i] = dp[i-1]+cost[0]。如果 i-7>=0，用 dp[i-7]+cost[1] 更新 dp[i]，否则用 cost[1] 更新。如果 i-30>=0，用 dp[i-30]+cost[1] 更新 dp[i]，否则用 cost[2] 更新。否则，dp[i] = dp[i-1]，不需要购票 
4. return dp[n]
5. 空间不太好，但是做出来了
6. 题解思路：（1）记忆化搜索（日期变量型）（2）记忆化搜索（窗口变量型）

相关问题

1. 急急急急急急我是急急国王
2. 确实感觉是动态规划
3. 忽略了当天不需要旅行的情况
4. 出了很多小 bug，i-7 小于 0 的情况忘记考虑了，

func mincostTickets(days []int, costs []int) int {
    n:=days[len(days)-1]
    dp:=make([]int,n+1)
    set:=map[int]bool{}
    for _,day:=range days {
        set[day]=true
    }
    dp[days[0]]=min(costs[0],min(costs[1],costs[2]))
    for i:=days[0]+1;i<=n;i++ {
        if set[i] {
            dp[i]=dp[i-1]+costs[0]
            if i-7>=0 {
                dp[i]=min(dp[i],dp[i-7]+costs[1])
            }else {
                dp[i]=min(dp[i],costs[1])
            }
            if i-30>=0 {
                dp[i]=min(dp[i],dp[i-30]+costs[2])
            }else {
                dp[i]=min(dp[i],costs[2])
            }
        }else {
            dp[i]=dp[i-1]
        }
    }
    //fmt.Println(dp)
    return dp[n]
}
func min(a,b int)int {
    if a<b {
        return a
    }
    return b
}