动态规划最低票价

前言：之前看到过这个题目归结到动态规划，当初还没什么思路，其实就是定义好dp [ i ] 为到第 i 个的最小费用就行，我们可以用upper_bound来优化我们的查找下标

题目地址

class Solution {
public:int mincostTickets(vector<int>& days, vector<int>& costs) {int n = days.size(), m = costs.size();vector<int> ans(n+2,0x3f3f3f3f);ans[0] = 0;// ans[ i ] 表示的是到 i 这个位置的最小费用int tian[] = {1,7,30};for(int i=0;i<n;i++){int u = days[i];for(int j=0;j<m;j++){int cost = costs[j];int pos = upper_bound(days.begin(),days.end(),u-tian[j])-days.begin();ans[i+1] = min(ans[i+1],ans[pos]+cost);}}return ans[n];// 到达 n 的最优解}
};