如何找到可以用4美分，6美分，10美分的郵費分成幾美分的方式？

Question

例如，

N = 4（4×1）1種方式

N = 10（4X1，6X1）（10×）2種方式

是否有任何方程可以表達的方式是多少？

Answer 1

您已使用recurrence-relation標記 - 是的，可以使用循環來計算方法的數量。

P(N) = P(N-10) + P(N-6) + P(N-4) 
P(0) = 1 

說明 - 您可以使用（N-10）美分總和和10美分硬幣等等獲得總和N。 對於相當大的N遞歸算法值將工作太長，因此可以構建動態編程算法以加速計算（DP將重新使用計算得到的較小和的值）

Answer 2

假設您有一個名單列表。在你的情況下，它是A = [4,6,10]。因此，假設你有以下幾件事：

A = [4,6,10] 
Length of list A = N 
Sum = K 

問題可以寫爲：

# Given the list of denominations, its length and the sum. 
P(A,N,K) = 0 if N < 0 or K < 0, 
      1 if K = 0, 
      P(A,N-1,K) + P(A,N-1,k-A[N]) #A[N]-> Nth element of list 

正如我們所看到的重新使用的子問題，將DP奇妙的工作的可能性。