【动态规划】【C++】最低票价问题_c++多短途的最小成本问题的动态规划算法实现

问题描述：
在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行。在接下来的一年里，你要旅行的日子将以一个名为 $days$ 的数组给出。每一项是一个从 $1$ 到 $365$ 的整数。

火车票有三种不同的销售方式：

一张为期一天的通行证售价为 $costs[0]$ 美元；
一张为期七天的通行证售价为 $costs[1]$ 美元；
一张为期三十天的通行证售价为 $costs[2]$ 美元。
通行证允许数天无限制的旅行。 例如，如果我们在第 $2$ 天获得一张为期 $7$ 天的通行证，那么我们可以连着旅行 $7$ 天：第 $2$ 天、第 $3$ 天、第 $4$ 天、第 $5$ 天、第 $6$ 天、第 $7$ 天和第 $8$ 天。

返回你想要完成在给定的列表 $days$ 中列出的每一天的旅行所需要的最低消费。

---

输入描述：
第一行输入 $nums$ 表示有 $nums$ 组测试
对每组测试用例
第一行输入 $m$
第二行输入具有 $m$ 个元素的 $days$ 数组，$days[i]$ 表示你将在 $days[i]$ 这天旅行
第三行输入具有 $3$ 个元素的 $costs$ 数组，具体释义见问题描述

输入示例：
2
6
1 4 6 7 8 20
2 7 15
12
1 2 3 4 5 6 7 8 9 10 30 31
2 7 15

---

输出描述：
对每组测试数据，输出你想要完成在给定的 $days$ 数组中列出的每一天的旅行所需要的最低消费。

输出示例：
11
17

---

没啥用的提示：
$1<=days.length<=365$
$1<=days[i]<=365$
$days$ 按顺序严格递增
$costs.length==3$
$1<=costs[i]<=1000$

---

思路：
每一天（或者说每一个旅行日），我们的花费都与今天以前之前所作的决策有关。我可以购买一张一天通行证，也可以在七天之前就买了一张七天通行证或者在三十天之前就买了一张三十天通行证。最后当然取三种情况里面花费最小的那个。转化为状态转移方程就如下所示。

$$dp[n]=min(dp[max(0,n-1)]+cost[0],dp[max(0,n-7)]+cost[1],dp[max(0,n-30)]+cost[2])$$

其中 $n$ 代表第 $n$ 天，$dp[n]$ 代表了到第 $n$ 天为止所需要的最低消费。

因为一年只有 $365$ 天，所以 $dp$ 数组最多只有 $365$ 个元素（加上无意义的 $0$ 可能有 $366$ 个），且每个元素只要一次就能求解，也就是说该算法的复杂度仅为 $O(365)=O(1)$ 。

---

源代码：

//
//  main.cpp
//  minTicketsCost
//
//  Created by 胡昱 on 2021/12/20.
//

#include <iostream>
using namespace std;

int main(int argc, const char * argv[]) {
    // 共nums组测试
    int nums;
    cin >> nums;
    while((nums--) > 0) {
        // 输入days数组
        int lengthOfDays;
        cin >> lengthOfDays;
        if(lengthOfDays <= 0) {
            // 处理极端情况
            cout << 0 << endl;
            continue;
        }
        int* days = new int[lengthOfDays];
        for(int i = 0; i < lengthOfDays; ++i) {
            cin >> days[i];
        }
        
        // 输入cost数组
        const int lengthOfCost = 3;
        int* cost = new int[lengthOfCost];
        for(int i = 0; i < lengthOfCost; ++i) {
            cin >> cost[i];
        }
        
        // 创建动态规划数组
        // dp[n]代表到第n天为止所需要的最低消费，因此共有366项元素（包括无意义的0）
        const int lengthOfDP = 366;
        int* dp = new int[lengthOfDP];
        // 初始化动态规划数组，即第1个旅行日之前的花费为0
        for(int n = 0; n < days[0]; ++n) {
            dp[n] = 0;
        }
        
        // 开始动态规划
        // 思路为：在旅行日时，我可以购买一张一天通行证、也可以在七天之前买一张七天通行证、也可以在三十天之前买一张三十天通行证，最后当然取三者最小
        // 因此动态规划在最后一个旅行日规划完成后就可以停止了，最终的结果为 dp[days[lengthOfDays - 1]]
        for(int i = 0; i < lengthOfDays; ++i) {
            int n = days[i];
            dp[n] = min(dp[max(0, n - 1)] + cost[0], min(dp[max(0, n - 7)] + cost[1], dp[max(0, n - 30)] + cost[2]));
            
            // 填满与下一个旅行日之间的动态规划数组
            if(i + 1 < lengthOfDays) {
                while((n++) < days[i + 1]) {
                    dp[n] = dp[n - 1];
                }
            }
        }
        
        // 输出结果并释放资源
        cout << dp[days[lengthOfDays - 1]] << endl;
        delete [] days;
        delete [] cost;
        delete [] dp;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67