動態規劃，要求最小值，我們首先可以嘗試使用狀態轉移表，使用一維陣列就可以了：
class Solution {
public:
int mincostTickets(vector<int>& days, vector<int>& costs) {
int help[3] = {1,7,30};//和costs一一對應
int n = days.size();
int len = days[n-1] - days[0] + 1;//旅行的日期跨度
vector<int> f(len + 1, INT_MAX);
//BFS，狀態轉移表
for(int i = 0; i < costs.size(); ++i){//特殊處理第一個階段的狀態
if(help[i] <= len) f[help[i]] = costs[i];//到第help[i]天的時候，消費的價格
else f[len] = min(f[len], costs[i]);
}
//只考慮需要出行的日子
for(int i = 1; i < n; ++i){//最多會有 i 個階段
int idx = days[i] - days[0] + 1;//當前時間對應在f中的下標+1爲idx
for(int k = 0; k < idx; ++k){//狀態只能從當前狀態之前的狀態轉移過來
if(f[k] != INT_MAX){
for(int j = 0; j < costs.size(); ++j){//每次都可以買不同天數的票
int tmp = idx + help[j] - 1; //選擇的票會轉移到f[tmp]狀態
if(tmp <= len) f[tmp] = min(f[tmp], f[k] + costs[j]);//是從狀態k轉移過來
else f[len] = min(f[len], f[k] + costs[j]);//長度超出索引就只能轉移到f[len]，即最後一個狀態
}
f[k] = INT_MAX;//之前的狀態已經轉移，轉移過的狀態就不再需要了
}
}
}
return f[len];
}
};
不過上面的程式碼寫的思路不是很清晰。。。
今天買哪種通行證，得看後幾天怎麼安排，即前面依賴後面–>從後向前來買。
看了題解之後才覺得這題我想的太複雜了-_-
dp[i] = min(決策1, 決策2, 決策3);//第 i 天開始，所需的最小費用
= min(c[0] + 1天後 天後不包, c[1] + 7天後 天後不包, c[2] + 30天不包);
= min(c[0] + dp[i + 1], c[1] + dp[i + 7], c[2] + dp[i + 30]);
官方題解的：
class Solution {
public:
unordered_set<int> dayset;//set方便查詢
vector<int> costs;
vector<int> memo;
int dp(int i){
if(i > 365) return 0;
if(memo[i] != -1) return memo[i];
if(dayset.count(i)){
memo[i] = min(min(dp(i+1) + costs[0], dp(i + 7) + costs[1]), dp(i + 30) + costs[2]);
}else
memo[i] = dp(i + 1);
return memo[i];
}
int mincostTickets(vector<int>& days, vector<int>& costs) {
this->costs = costs;
memo = vector<int>(366, -1);
for(const auto &c : days) dayset.insert(c);
return dp(1);
}
};
這兒的圖解可以看一下，畫的挺清晰：
[java] 動態規劃思路步驟 (從後向前迭代) - 最低票價 - 力扣（LeetCode）
class Solution {
public:
int mincostTickets(vector<int>& days, vector<int>& costs) {
int len = days.size();
int maxDay = days[len - 1], minDay = days[0];
vector<int> dp(maxDay + 31, 0);//簡化邊界的判斷，反正多出來的初始化爲0
for(int d = maxDay, i = len - 1; d >= minDay; --d){//從後往前
//i 表示days的索引
if(d == days[i]){//只考慮需要出行的日子
dp[d] = min(dp[d + 1] + costs[0], dp[d + 7] + costs[1]);
dp[d] = min(dp[d], dp[d + 30] + costs[2]);
--i;
}else dp[d] = dp[d + 1];
}
return dp[minDay];
}
};
其實從前往後也是可以的，只是不太好理解：