最近在練習演算法
剛好寫到一個標準的硬幣問題
https://leetcode.com/problems/coin-change/
本來用DP寫，發現只beat 70%
參考別人的寫法後，發現這題很多人都用DFS寫
於是寫了一個版本(DFS)結果time limit exceeded
後來改了一個版本(DFS2)
DFS2只是簡單的將原本的return判斷式移動到進入遞迴之前，結果時間卻差很多
當然能理解多進一層遞迴確實成本有差
但是從時間複雜度來看，order應該一致的？
主要想請教原本寫法會time limit exceeded是否只是單純進遞迴成本差太多？
或著有其他因素在？
程式碼：
https://goo.gl/e7ZEBq
[額外請教一個github問題]
我每次編輯程式碼都會將tab的縮排長度設定為4
但是存檔後打開，看起來都自動跳回8
用筆電的話反而會自動跳為2
不知道要如何將它真的固定為4
※ 編輯: worcdlo (42.73.253.241), 01/10/2019 06:41:56
1F：推 kaneson: 雖然沒幫你驗證你的code，直覺上來看這是有剪枝跟沒剪枝 01/10 07:08
2F：→ kaneson: 的差別，不是只有省掉call func 01/10 07:08
我自己看起來是覺得都有剪，只是第一個版本要進入下一層function才剪
另外因為連結更動用手機編輯，不知道為何就把更早的兩個回文刪了，真是抱歉
※ 編輯: worcdlo (123.195.174.95), 01/10/2019 09:21:21
3F：推 kaneson: 我沒有看題目純分享經驗，for裡面多加了個if-then break 01/10 12:02
4F：→ kaneson: 兩者展開樹長相應該差挺多的。另外想提時間複雜度部分， 01/10 12:02
5F：→ kaneson: 書本理論只是討論分級，假設某二者同級但差常數倍實機上 01/10 12:02
6F：→ kaneson: 會有感很正常，隨著硬體換新，差異感會漸漸縮小。 01/10 12:02
7F：推 IhateOGC: 看你目的是為了效率還是好維護 01/10 18:26
8F：→ IhateOGC: 通常大型專案會朝向好維護，硬體花錢就有 01/10 18:26
9F：→ IhateOGC: 一堆Bug無法維護的code硬體效能再好都沒用 01/10 18:27
10F：推 IhateOGC: 一個function包了5000行和一個function500行的差異 01/10 18:30
11F：→ IhateOGC: 效能可能差不到1/10000 01/10 18:31
12F：推 Astar5566: 這題要DP吧!? 怎麼會爆搜剪枝 01/10 22:49
13F：→ Astar5566: 至於你問的問題 其實不只插在有沒有call 01/10 22:51
14F：→ Astar5566: 不只差在有沒有call 那個for迴圈沒有break的話 01/10 22:52
15F：→ Astar5566: 也會多很多call出來 01/10 22:52