Leetcode 983. 最低票价 动态规划
原题链接：Leetcode 983. 最低票价
class Solution {
public:
int mincostTickets(vector<int>& days, vector<int>& costs) {
int n = days.size();
int last = days[n - 1];
int dp[last + 1];
map<int, int> mp;
for (auto x : days)
mp[x] = 1;
dp[0] = 0;
int v1[3] = {1, 7, 30};
for (int i = 1; i <= last; i++) {
if (mp[i]) {
dp[i] = INT_MAX;
for (int k = 0; k < 3; k++) {
dp[i] = min(dp[i], dp[max(i - v1[k], 0)] + costs[k]);
}
} else {
dp[i] = dp[i - 1];
}
}
return dp[last];
}
};