leetcode每日一题983. 最低票价（动态规划）_在一个火车旅行很受欢迎的国度,你提前一年计划了一些火车旅行。在接下来的一

思路

不是很难的动态规划，但是最开始一些边界条件没考虑到，WA了好几次，然后面向测试用例debug。
设dp[i]为前i天（含）旅游花费的最小金额。
dp[i] = min{dp[i-1] + costs[0], dp[i-7] + costs[1], dp[i-30]+costs[2]}
然后两个旅游日之间的日子旅游最小花费就等于前一个旅游日的最小花费。即dp[j] = dp[days[i]]，days[i] < j < days[i+1]

代码

class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        int duration[3] = {1, 7, 30};
        vector<int> dp;
        int lastday = days[days.size()-1];
        int firstday = days[0];
        dp.resize(lastday+1);
        fill(dp.begin(),dp.end(),0x3f3f3f3f);
        fill(dp.begin(),dp.begin()+firstday,0);
        for(int i=0;i<3;i++)
            dp[firstday] = min(dp[firstday],costs[i]);
        for(int i=1;i<days.size();i++)
        {
            int nowday = days[i];
            for(int day=days[i-1]+1;day<nowday;day++)
                dp[day] = dp[days[i-1]];
            for(int j=0;j<costs.size();j++)
            {
                if(nowday-duration[j]>=1)
                    dp[nowday] = min(dp[nowday],dp[nowday-duration[j]]+costs[j]);
                else dp[nowday] = min(dp[nowday],dp[0]+costs[j]);
            }
        }
        return dp[lastday];
    }
};
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