このアルゴリズムは、10 セント硬貨、5 セント硬貨、および 1 セント硬貨のみを使用して、入力金額を変更できる方法の数を見つけることになっています。私のアプローチは、分割統治戦略を使用し、最大のコインである 1 セント硬貨を使用して変更を行う方法の数と、1 セント硬貨を使用せずに変更を行う方法の数を見つけることによって、問題を分割することでした。1 ～ 14 の入力に対して問題を正しく解決するこのアルゴリズムの実装を作成しましたが、入力が 15 以上の場合、返される結果は正しくありません。明らかに私のアルゴリズムは間違っており、コードを修正するためにどのような変更を加える必要があるか、また私のアプローチが適切な分割統治ソリューションであるかどうか疑問に思っていました。
コードは次のとおりです。
public static int makeChange(int n) {
if(n < 0)
return 0;
else {
int sum = makeChange(n-10) + makeChange(n-5) + 1;
return sum;
}
}
どうもありがとう。