LeetCode 983. 最低票价_用1天,7天,30天的钱数java实现

题目描述：

解法：

class Solution {
public:
    int mincostTickets(vector<int>& days, vector<int>& costs) {
        int n=days.size();
        vector<int> dp(n+1,0);            //设置n+1个位置，每个位置代表第days[i-1]天的最小花费
        int last7,last30;                 //动态规划，上一个必须另外付钱的索引
        for(int i=1;i<=n;i++){
            last7=lower_bound(days.begin(),days.begin()+i-1,days[i-1]-6)-days.begin();
            last30=lower_bound(days.begin(),days.begin()+i-1,days[i-1]-29)-days.begin();
            dp[i]=min(costs[0]+dp[i-1],min(costs[1]+dp[last7],costs[2]+dp[last30]));
        }
        return dp[n];
    }
};
/*第i天的最小钱数 = min ( 第i-1天的最小钱数+1天票钱costs[0] , 第i-7天的最小钱数+7天票钱costs[1] ,第i-30天的最小钱数+30天票钱costs[2])*/