find 1,5,10,25,50セントを使用して合計17cents（たとえば）を取得する方法の数

Question

なぜスタックオーバーフローエラーが発生するのですか？これは私が開始する前に再帰的にこれを解決しようとしていますダイナミックプログラミングを使い始める。メソッドコインでは、 "a"は、私が望む合計を形成するコインを保持する配列であり、sumは合計（例えば17）であり、iは配列iのインデックスを表すamで

import java.util.*; 
public class dp2 {//RECURSIVE WAY THEN OPTIMIZE TO DP 
    public static int coins (int [] a, int sum,int i){ 

    if (sum==0) 
     return 1; 
    else if (i==a.length){ 
     return 0; 
    } 
    else if (i>a.length&&sum<a[i]){ 
     return coins(a,sum,i++); 
    } 

    else { 
     return coins(a,sum-a[i],i++)+coins(a,sum-a[i],i); 
    } 
    } 

    public static void main (String [] args){ 
    Scanner sc = new Scanner (System.in); 

    while (sc.hasNext()){ 
     int x = sc.nextInt(); 
     int y=x; 
     int [] a ={1,5,10,25,50}; 
     int w = coins(a,y,0); 
     System.out.println("There are " +w+ " ways to produce "+x + " coins change."); 
    }    
    } 

} 

Answer 1

あなたは無限ループに問題があります。

最初にチェックしてください、実際には1または0だけを返すことができるので、何を返すのですか。だから、他の条件はどこですか？例：i == a.length - 1または合計<？私は、あなたが合計を返したいと思います。

次に、例17を入力すれば、どこから選択することができますか？

と次、私が常にあるので、あなたのコードでは、return coins(a,sum-a[i],++i)+coins(a,sum-a[i],i);を変更してください0

ので、たぶん、あなたのために良いexapleコードです：私はあなたのコードに1文を追加

class dp2 {//RECURSIVE WAY THEN OPTIMIZE TO DP 
    public static int coins (int [] a, int sum,int i){ 
    if (sum==0) 
     return 1; 
    else if (i==a.length){ 
     return 0; 
    }else if(i + 1 == a.length || sum < 0 || sum - a[i] < 0){ //Your break condition ? 
     return sum; 
    } 
    else if (i>a.length&&sum<a[i]){ 
     return coins(a,sum,i++); 
    } 

    else { 
     return coins(a,sum-a[i],++i)+coins(a,sum-a[i],i); 
    } 
    } 
    public static void main (String [] args){ 
    Scanner sc = new Scanner (System.in); 

    while (sc.hasNext()){ 
     int x = sc.nextInt(); 
     int y=x; 
     int [] a ={1,5,10,25,50}; 
     int w = coins(a,y,0); 
     System.out.println("There are " +w+ " ways to produce "+x + " coins change."); 
    } 
    } 
} 

Answer 2

、 4行目で：

System.out.println(sum + ", " + i); 

入力27を与え、出力は次の通りであった：

27, 0 
26, 0 
25, 0 
.... decreasing by one each time... 
3, 0 
2, 0 
1, 0 
0, 0 
-4, 1 
-9, 1 
-14, 1 

sum < 0をチェックしていないため、停止しません。

あなたはそこからそれを把握することができるはず... println：世界で最軽量のデバッガ