動態規劃就是把一系列問題拆分成一個一個的子問題的程序 ，例如我們的斐波那契數列問題，可以從最后一個序列的加減法看起，這樣就可以使用遞回得到最后的結果了，
除了斐波那契數列，我們還有什么問題也是dp的問題呢？
問題：給定一個n，找到不同的n將其寫成1，3，4相加的方法，
當n=5時，答案是6，一共有6中組合方式，如下：
5=1+1+1+1+1
=1+1+3
=1+3+1
=3+1+1
=1+4
=4+1
因此我們可以從最后一個數字看起，假設數字n一共有D（n）種組合的方式，那么我們假設最后一個數字我們加上的是1，則加到倒數第二個數字時有D（n-1）種組合方法，假設最后加上的是3，則有D（n-3）種方法，假設最后加上的是4，則有D（n-4）種方法，
所以我們可以得到公式：
D(N)=D(N-1)+D(N-3)+D(N-4)
這樣就可以使用遞回求解了，遞回的時間復雜度是2^n，就是時間復雜度有點高，代碼如下：
def dp(n): if n==1: return 1 if n==2: return 1 if n==3: return 2 if n==4:# 1,3 3,1 1,1,1,1 4 return 4 #1，3，4 return dp(n-1)+dp(n-3)+dp(n-4)
大家可以思考一下迭代的解法
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/145124.html
標籤：其他