主題
題目連結：
題目意譯：
你給定一整數 total 代表著你有的金錢額度。你同時也被給定兩正數 cost1 和 cost2，依序代表著一支墨水筆以及一支鉛筆的價格。你可以使用你部分或全部的錢來購買若干數量（可能沒有）的每一種書寫工具。
回傳你可以購買若干數量的墨水筆和鉛筆的所有方法數。
限制：
1 ≦ total, cost1, cost2 ≦ 10 ^ 6
範例測資：
範例 1：
輸入： total = 20, cost1 = 10, cost2 = 5
輸出： 9
解釋： 墨水筆的價格為 10，而鉛筆的價格為 5。
- 如果你買了 0 支墨水筆，則你可以買 0 、 1 、 2 、 3 或 4 支鉛筆。
- 如果你買了 1 支墨水筆，則你可以買 0 、 1 或 2 支鉛筆。
- 如果你買了 2 支墨水筆，則你買不了任何鉛筆。
購買墨水筆以及鉛筆的方法數為 5 + 3 + 1 = 9。
範例 2：
輸入： total = 5, cost1 = 10, cost2 = 10
輸出： 1
解釋： 墨水筆和鉛筆皆為 10，兩者都超過 total，因此你買不了任何的書寫工具。因此只有一種方式：買 0 支墨水筆和 0 支鉛筆。
解題思維：
可以看到當我們固定墨水筆（或鉛筆）的數量的時候，便可以快速地算出鉛筆（或墨水筆）會有多少種購買方式，也就是說：
假設我們先買了 k 支墨水筆（可以看到 0 ≦ k ≦ total ÷ cost1），則剩下的金額為 total - cost1 × k（令此值為 m）。此時可以看到我們可以買 0 、 1 、 …… 、「m ÷ cost2 取整」支鉛筆，總共是「m ÷ cost2 取整」 + 1 種方式。
因此我們就窮舉所有的 k 值，算出各自有多少種鉛筆購買方式，全數加總即為所求。
時間複雜度為 O(total ÷ cost1)。如果考慮誰的 k 值範圍比較小的話，可以變成 O(total ÷ max(cost1, cost2))。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人
