這是個旅行規劃的情境，會給你一個陣列代表你要玩的日子，還有一個陣列代表三種不同的機票價錢
日子就包含1~365，也就是一年的第1天到第365天
機票價錢分為三種，1日票、7日票和30日票
買一次7日票表示從那天開始算那7天之內你想隨便搭就怎麼搭，30日票就是30天
要計算出這趟旅行能夠花的最低價錢
舉個例：
Input: days = [1,4,6,7,8,20], costs = [2,7,15] Output: 11 Explanation: For example, here is one way to buy passes that lets you travel your travel plan: On day 1, you bought a 1-day pass for costs[0] = $2, which covered day 1. On day 3, you bought a 7-day pass for costs[1] = $7, which covered days 3, 4, ..., 9. On day 20, you bought a 1-day pass for costs[0] = $2, which covered day 20. In total you spent $11 and covered all the days of your travel.
Sol：
先說這題我覺得有點難... 因為這是我第一題Dynamic Programming的題目，只是現在才貼上來
然後我一開始根本沒這個概念，完全不知道怎麼辦XD
回到題目，這又是個Dynamic Programming的問題
不過怎麼做是個重點
照一般的邏輯，從第一天開始往後推，的確是能夠推出答案
大概長這樣子：
int mincostTickets(vector<int>& days, vector<int>& costs) {
int memo[366];
memset(memo, 0, sizeof(memo));
for (int day = 1; day <= 365; ++day)
{
if(find(days.begin(), days.end(), day) == days.end())
{
memo[day] = memo[day - 1]; // 如果這天沒有在行程中，那到這天為止的最小花費就等於前一天的花費
}
else
{
memo[day] = min({memo[max(0, day - 1)] + costs[0],
memo[max(0, day - 7)] + costs[1],
memo[max(0, day - 30)] + costs[2]}); // 看看哪種花費最少就記錄起來
}
}
return memo[days.back()];
}
這大概是最容易想到的方法，也是我唯一能夠自己寫出來的方法...
一天一天的算下去就對了
接下來講一個... 稍微難懂的方法吧，我看了老半天XD
另一種觀點就是只看要去的那幾天
具體是什麼個想法呢
這就要用到遞迴了...
我們先來看code吧，加上註解之後如果還是不太懂再來解釋：
vector<int> m_days;
vector<int> m_costs;
vector<int> m_memo;
vector<int> m_duration = {1, 7, 30};
int mincostTickets(vector<int>& days, vector<int>& costs) {
for (int i = 0; i < days.size(); ++i)
{
m_memo.emplace_back(0); // 首先初始化m_memo
}
sort(days.begin(), days.end()); // 這邊有排序，因為一定要排序
m_days = days;
m_costs = costs;
return dp(0); // dp(i)表示的是：從第days[i]到結束所需要的最小花費
}
int dp(int i)
{
if (i >= m_days.size())
return 0;
if (m_memo[i] != 0)
return m_memo[i];
int ans = INT_MAX;
int j = i;
for (int k = 0; k < 3; ++k) // 這邊要算三種情況，然後得出最小的
{
// m_days[j]如果小於m_days[i] + m_duration[k]，表示你再m_days[i]買了這個duration的票之後m_days[j]也不用買票了，就可以跳過m_days[j]
while (j < m_days.size() && m_days[j] < m_days[i] + m_duration[k])
++j;
ans = min(ans, dp(j) + m_costs[k]); // 找到下一天要買票的日子m_days[j]之後，就加上那一天要買票的價錢，然後遞洄去算dp(j)
}
m_memo[i] = ans; // 算完之後存起來並回傳
return ans;
}
...是不是有點複雜
不過理解之後這個好像比較符合人的思考方式
有點類似從尾巴開始算的概念(遞迴會先跑到尾巴去算完再跳回來)
只是要實作出來不是那麼容易而已
但只要知道dp(i)代表的是什麼意思，應該就可以看懂code在做什麼了
有問題再說吧~ 這個我覺得大部分情況第一種作法比較簡潔又方便
有機會再傳一些類似的題目上來~
