欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Leetcode 983.最低票价

程序员文章站 2022-07-03 15:24:22
...

题目描述:
Leetcode 983.最低票价
这道题肯定是采用动态规划的方法。
1.设一个dp数组表示完成当前计划后的最小花费;
2.首先要处理出每一个一个计划日对于7天通行证和30天通行证的最优前计划日(即最小)。
3.假定每一天都买一张为期为一天的通行证,那么花费以costs[0]累加;
4.对于7天通行证来说,遍历从当前计划日的前计划日开始到当前计划日,比较得出最小的花费(min(dp[i],dp[j]+costs[1]))。
5.对于30天通行证来说,也同样如此。
最后得到的dp[len-1]就是要返回的答案。

代码:

class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        int len=days.size();
        if(len==1)return min(costs[0],min(costs[1],costs[2]));
        vector<int>pre2(len,0),pre1(len,0);
        vector<int>dp(len,0x3f3f3f3f);
        for(int i=0;i<len;i++)pre1[i]=pre2[i]=0x3f3f3f3f;
        for(int i=0;i<len;i++)
        {
            int pos1=upper_bound(days.begin(),days.end(),days[i]+6)-days.begin()-1;
            //pos1表示当前计划日使用了7天通行证的最后一个计划日
            pre1[pos1]=min(i,pre1[pos1]);
            for(int j=i+1;j<pos1;j++)
                pre1[j]=min(i,pre1[j]);
            //将这中间的所有计划日比较、赋值一遍
        }
        for(int i=0;i<len;i++)
        {
            int pos2=upper_bound(days.begin(),days.end(),days[i]+29)-days.begin()-1;
            //pos2表示当前计划日使用了30天通行证的最后一个计划日
            pre2[pos2]=min(i,pre2[pos2]);
            for(int j=i+1;j<pos2;j++)
                pre2[j]=min(pre2[j],i);
       }
        for(int i=0;i<len;i++)
        {
            if(i==0)dp[0]=costs[0];
            else
            {
                dp[i]=dp[i-1]+costs[0];//每一个计划日都是前一个加1天通行证的花费
                if(pre1[i]!=0x3f3f3f3f){
                	//遍历7天通信证能到达的每一个前计划日,比较出较小的
	                if(pre1[i]==0)dp[i]=min(dp[i],costs[1]);
	                else dp[i]=min(dp[i],dp[pre1[i]-1]+costs[1]);
	                for(int j=pre1[i];j<i;j++)
	                    dp[i]=min(dp[i],dp[j]+costs[1]);
                }
                if(pre2[i]!=0x3f3f3f3f){
                	//遍历30天通信证能到达的每一个前计划日,比较出较小的
	                if(pre2[i]==0)dp[i]=min(dp[i],costs[2]);
	                else dp[i]=min(dp[i],dp[pre2[i]-1]+costs[2]);
	                for(int j=pre2[i];j<i;j++)
	                    dp[i]=min(dp[i],dp[j]+costs[2]);
                }
            }
        }
        return dp[len-1];
    }
};
相关标签: Leetcode