これはコインチェンジチャレンジの正しい再発関係ですか？

Question

私は "コインの変更の問題"を解決しようとしています。私は再帰的な解決策を考案したと思いますが、確認したいと思います。

例として、ペニー、ニックル、ダイムがあり、22セントの変更をしようとしているとします。

C = { 1 = penny, nickle = 5, dime = 10 } 
K = 22 

その後の変化を作製するための多くの方法が等々

f(C,N) = f({1,5,10},22) 
= 
    (# of ways to make change with 0 dimes) 
+ (# of ways to make change with 1 dimes) 
+ (# of ways to make change with 2 dimes) 

= f(C\{dime},22-0*10) + f(C\{dime},22-1*10) + f(C\{dime},22-2*10) 
= f({1,5},22) + f({1,5},12) + f({1,5},2) 

と

f({1,5},22) 
= f({1,5}\{nickle},22-0*5) + f({1,5}\{nickle},22-1*5) + f({1,5}\{nickle},22-2*5) + f({1,5}\{nickle},22-3*5) + f({1,5}\{nickle},22-4*5) 
= f({1},22) + f({1},17) + f({1},12) + f({1},7) + f({1},2) 
= 5 

です。言い換えれば

ことで任意の欠陥があった場合、私のアルゴリズムは

let f(C,K) be the number of ways to make change for K cents with coins C 
and have the following implementation 

if(C is empty or K=0) 
    return 0 
sum = 0 
m = C.PopLargest() 
A = {0, 1, ..., K/m} 
for(i in A) 
    sum += f(C,K-i*m) 
return sum 

のようなものですか？

線形時間でしょうか。お使いのベースケースについて

Answer 1

再考：ロジックの

1. What if K < 0 ? Then no solution exists. i.e. No of ways = 0. 

2. When K = 0, so there is 1 way to make changes and which is to consider zero elements from array of coin-types. 

3. When coin array is empty then No of ways = 0. 

残りは正しいです。しかしアルゴリズムがリニアであるというあなたの認識は絶対に間違っています。

• 最大要素であるポップO（C.length）：

  は、複雑さを計算できます。ただし、配列全体を最初にソートすることを検討する場合は、このステップは に最適化できます。

• あなたのforループは、すべての呼び出しと関数を再帰的に呼び出すすべての繰り返しでO（K/Cmax）回動作します。

だから、あなたはそれを繰り返し書く。

T(N) = O(N) + K*T(N-1) 

これはN（配列​​のサイズ）で指数関数的になります。

あなたが改善を探している場合は、動的プログラミングを使用することをお勧めします。