【LeetCode】每日一题 2024_10_1 最低票价（记忆化搜索/DP）

前言

每天和你一起刷 LeetCode 每日一题~

大家国庆节快乐呀~

LeetCode 启动！

题目：最低票价

代码与解题思路

今天这道题是经典动态规划，我们定义 dfs(i) 表示从第 1 天到 第 i 天的最小花费，然后使用祖传的：从记忆化搜索 -> 动态规划的思路开始解题

记忆化搜索：

func mincostTickets(days []int, costs []int) int {n := days[len(days)-1]needCost := make([]bool, n+1)for _, v := range days { // 记录需要通行证的日子needCost[v] = true}// 记忆化memo := make([]int, n+1)for i := range memo {memo[i] = -1}// i 表示第 1 天到 第 i 天的最小花费var dfs func(int) intdfs = func(i int) (res int) {if i <= 0 { // 不存在的情况就返回 0return 0}// 记忆化操作p := &memo[i]if *p != -1 {return *p}defer func() {*p = res}()if !needCost[i] { // 如果不需要通行证，那就不需要花费res = dfs(i-1)} else { // 选出三种花费中最小的一种res = min(dfs(i-1)+costs[0], dfs(i-7)+costs[1], dfs(i-30)+costs[2])}return res}return dfs(n)
}

记忆化搜索转递推：

func mincostTickets(days []int, costs []int) int {n := days[len(days)-1]needCost := make([]bool, n+1)for _, v := range days {needCost[v] = true}f := make([]int, n+1)for i := 1; i < len(f); i++ {if !needCost[i] {f[i] = f[i-1]} else { f[i] = min(f[i-1]+costs[0], f[max(i-7, 0)]+costs[1], f[max(i-30, 0)]+costs[2])}}return f[n]
}

基本上一比一复刻就可以啦~

有一个需要注意的点，在使用状态转移方程的时候：min(f[i-1]+costs[0], f[max(i-7, 0)]+costs[1], f[max(i-30, 0)]+costs[2])，这里用了 max(i-7, 0) 和 max(i-30, 0)，其实就是记忆化搜索中的：

if i <= 0 {return 0
}

如果不存在这种情况，就返回 0，不记入总花费。

视频实况

[【【LeetCode】每日一题 2024_10_1 最低票价（记忆化搜索/DP）】 ]( https://www.bilibili.com/video/BV19CxheNETm/?share_source=copy_web&vd_source=5838aabca6ee756488292563a3936f1d

每天进步一点点

可以和我刷一辈子的每日一题吗？
一题一题，积累起来就是一辈子。