198、【动态规划】leetcode ——983. 最低票价:记忆化搜索(C++版本)
题目描述
Problem: 983. 最低票价
思路
本题是根据
days
中的行程表,找到一个最小费用的购票方案。通常,当没有连续天数出行时,是购买一天的更便宜。但题中有可能会有多天连续出行的情况,此时如果一下子购买多天的行程票,可能会比只够买一张更便宜。因此,本题就是要找到当到达某一天时,是由一天前买的票到达当天更便宜,还是由七天前或三十天前到达当天更便宜。
解题方法
- 动态规划五步曲:
(1)dp[i]含义: 第i天时,所需要的最低消费。
(2)递推公式: d p [ i ] = m i n ( d p [ i − 1 ] + c o s t [ 0 ] , d p [ i − 7 ] + c o s t [ 1 ] , d p [ i − 30 ] + c o s t [ 2 ] ) dp[i] = min(dp[i - 1] + cost[0], dp[i - 7] + cost[1], dp[i - 30] + cost[2]) dp[i]=min(dp[i−1]+cost[0],dp[i−7]+cost[1],dp[i−30]+cost[2]),从上述三种情况中反推出来那种情况到达第i天时开销最小。
(3)dp数组初始化: dp[0] = 0,天数从1到n,0不合法为了便于计算dp[0]=0。而目标是求min,因此其余值设为INT_MAX。
(4)遍历顺序: 从左到右,按天数增长依次遍历。(这里注意,有可能会由7天或30天的票价,比1天的票价便宜的情况)
(5)举例:
复杂度
- 时间复杂度:
添加时间复杂度, 示例: O ( n ) O(n) O(n)
- 空间复杂度:
添加空间复杂度, 示例: O ( n ) O(n) O(n)
Code
class Solution {
public:
int mincostTickets(vector<int>& days, vector<int>& costs) {
int n = days.back();
vector<int> dp(n + 1, INT_MAX);
dp[0] = 0;
vector<int> has_trip(n + 1,false);
for(int i = 0; i < days.size(); i++) has_trip[days[i]] = true;
for(int i = 1; i <= n; i++) {
if(has_trip[i] == false) {
dp[i] = dp[i - 1];
} else {
// 这里让b和c在小于0时,不变为0的原因是因为可能会有7天或30天的票,比1天的票更便宜的情况
int a = dp[i - 1] + costs[0];
int b = i - 7 >= 0 ? dp[i - 7] + costs[1] : costs[1];
int c = i - 30 >= 0 ? dp[i - 30] + costs[2] : costs[2];
dp[i] = min(a, min(b, c));
}
}
return dp[n];
}
};
相关文章
- 【C/C++学院】(4)c++开篇/类和对象/命名空间/类型增强/三目运算符/const专题/引用专题/函数增强
- c++ 动态解析PE导出表
- Hash表的C++实现(转)
- C/C++基础讲解(六)之基础例程3篇
- Open3D(C++) RANSAC点云粗配准(基于FPFH)
- Open3D(C++) 快速全局配准(基于FPFH)
- 有关C,C++,C#, Java的图形图像处理类库 整理(未完待续)
- paip.c++ qt 外部dll共享库的导入以及引用
- C++设计模式:原型模式
- Qt 纯C++项目发布为dll的方法(超详细步骤)
- [h5棋牌项目]-15-C#与C++通信
- 【华为OD机试 2023】 查找重复代码(C++ Java JavaScript Python)
- 【华为OD机试 2023】 快速开租建站(C++ Java JavaScript Python)
- 解答私信@被c++折磨头秃的花季美少女 //C++ 利用指针数组输入10个单词,编写函数对10个单词进行排序并输出,要求判断是否有相同的单词,如果有相同的单词在输出时该单词只输出一次。
- C/C++每日面试之句子的逆序
- LeetCode 整数转罗马数字(执行用时: 12 ms , 在所有 C++ 提交中击败了 32.38% 的用户)
- Leetcode 两数之和 C / C++
- C++ primer札记10-继承
- AI模型C++部署:ubuntu安装Cython并使用C/C++调用python动态库【附加c++与python互相调用算法demo程序接口的源码】
- c++ 函数签名
- C/C++:C++友元类
- C++里怎么样让类对象删除时自动释放动态分配的内存?
- 【TDengine】一篇文章了解 C++ 操作 TDengine(详解)
- 基于新版OpenCV5(C++)+OpenVINO Toolkit案例算法模型示例使用(一条语义分割与目标检测示例搞懂OpenVINO模型部署机制)
- C++的学习心得和知识总结 第四章(完)