數字拆解問題

最近在找工作，有家公司寄了一個題目給我，要我作答，題目不難，有興趣可以看看： #數字拆解 題目是這樣的： 3 = 2+1 = 1+1+1 所以3有三種拆法 4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1 共五種 5 = 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 +1 +1 +1 共七種 依此類推，請問一個指定數字NUM的拆解方法個數有多少個？ #建議方案(也可使用其他方法) 6 = 5 + [1] = 4 + [1+1] = 3 + [1+1+1] = 2 + [1+1+1+1] = 1 + [1+1+1+1] = 2 + [2+1+1] = 3 + [2+1] 4 + [2] = 2 + [2+2] 3 + [3] *括弧內數字為固定數字,最大數字繼續拆解 *拆解過程中,數字須由大到小 #請計算出Num=40共多少解法,需花多少時間(須印出所有合法解法) num = 40, count = 37337, time = 1.188 想不到他的最後答案竟然是錯的，還真是有一點點心機。過兩天再把答案 po 上來。