最近在練習演算法
剛好寫到一個標準的硬幣問題
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
推 kaneson: 雖然沒幫你驗證你的code，直覺上來看這是有剪枝跟沒剪枝
→ kaneson: 的差別，不是只有省掉call func
我自己看起來是覺得都有剪，只是第一個版本要進入下一層function才剪
另外因為連結更動用手機編輯，不知道為何就把更早的兩個回文刪了，真是抱歉
※ 編輯: worcdlo (123.195.174.95), 01/10/2019 09:21:21
推 kaneson: 我沒有看題目純分享經驗，for裡面多加了個if-then break
→ kaneson: 兩者展開樹長相應該差挺多的。另外想提時間複雜度部分，
→ kaneson: 書本理論只是討論分級，假設某二者同級但差常數倍實機上
→ kaneson: 會有感很正常，隨著硬體換新，差異感會漸漸縮小。
推 IhateOGC: 看你目的是為了效率還是好維護
→ IhateOGC: 通常大型專案會朝向好維護，硬體花錢就有
→ IhateOGC: 一堆Bug無法維護的code硬體效能再好都沒用
推 IhateOGC: 一個function包了5000行和一個function500行的差異
→ IhateOGC: 效能可能差不到1/10000
推 Astar5566: 這題要DP吧!? 怎麼會爆搜剪枝
→ Astar5566: 至於你問的問題 其實不只插在有沒有call
→ Astar5566: 不只差在有沒有call 那個for迴圈沒有break的話
→ Astar5566: 也會多很多call出來