光速东莞网站建设,杭州知名的互联网公司,小皮搭建本地网站,做了网站应该如何推广前言
每天和你一起刷 LeetCode 每日一题~
大家国庆节快乐呀~
LeetCode 启动#xff01; 题目#xff1a;最低票价 代码与解题思路
今天这道题是经典动态规划#xff0c;我们定义 dfs(i) 表示从第 1 天到 第 i 天的最小花费#xff0c;然后使用祖传的#xff1a;从记忆…前言
每天和你一起刷 LeetCode 每日一题~
大家国庆节快乐呀~
LeetCode 启动 题目最低票价 代码与解题思路
今天这道题是经典动态规划我们定义 dfs(i) 表示从第 1 天到 第 i 天的最小花费然后使用祖传的从记忆化搜索 - 动态规划的思路开始解题
记忆化搜索
func mincostTickets(days []int, costs []int) int {n : days[len(days)-1]needCost : make([]bool, n1)for _, v : range days { // 记录需要通行证的日子needCost[v] true}// 记忆化memo : make([]int, n1)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, n1)for _, v : range days {needCost[v] true}f : make([]int, n1)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_sourcecopy_webvd_source5838aabca6ee756488292563a3936f1d
每天进步一点点 可以和我刷一辈子的每日一题吗 一题一题积累起来就是一辈子。
