最低票价（dp）_最低票价 dp

const int max_value = 65536;
class Solution {
public:
	int mincostTickets(vector<int>& days, vector<int>& costs) {
		//dp[i]表示到第i天为止花费的最少路费
		int len = days.size();//需要出行的天数
		int n = days[len - 1];
		vector<int>dp(n + 1, 0);
		dp[0] = 0;//初始化
		for (int i = 0; i < len; i++)//标记出需要出行的日子
		{
			dp[days[i]] = max_value;
		}
		for (int i = 1; i <= n; i++)
		{
			if (dp[i] == 0)//表示第i天不需要出行，那么第i天自然不用花钱
				dp[i] = dp[i - 1];
			else
			{
				dp[i] = min({ dp[i - 1] + costs[0], dp[max(0,i - 7)] + costs[1], dp[max(0,i - 30)] + costs[2] });
				// 如果一月前，买了月票，会不会更便宜？
				// 如果一周前，买了周票，会不会更便宜？
				// 如果都不会的话，那我暂时先买日票试试呗

			}

		}
		return dp[n];
	}
};
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