LeetCode 983. 最低票价（从前向后dp）

题目

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

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

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

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

样例

---

题解

从前向后dp
$dp[i]$dp[i]是第$i$i天的最少花费
如果第$i$i天不用出门$dp[i]=dp[i-1]$dp[i]=dp[i−1]
如果第$i$i天要出门，那么这天必须有票。
如果某张票的有效期是7天，那么为了让票物尽其用，就应该在7天前买这张票即，在第i-7+1天买这张票，这样所花费的钱就是dp[i-7]+票钱。如果7天前还没出门过，所花费的钱就是票钱。
每次要出门就遍历这3张票，取最小值

class Solution 
{
int vis[400]={0};
int can[3]={1,7,30};
int dp[400];
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) 
	{
		int last=days[days.size()-1]; 
		for(int i=0;i<days.size();i++)
		{
			vis[days[i]]=1;
		}
		for(int i=1;i<=last;i++)
		{
			if(!vis[i]) dp[i]=dp[i-1];
			else
			{
				dp[i]=1e9;
				for(int j=0;j<costs.size();j++)
				{
					if(i-can[j]<=0) dp[i]=min(dp[i],costs[j]);
					else dp[i]=min(dp[i],dp[i-can[j]]+costs[j]);
				}
			}
		}
		return dp[last];
    }
};

时间复杂度为$O(n)$O(n)