動的プログラミングの基本的なアイデアは、問題を分解していくつかのサブ問題に解決し、最初にサブ問題を解決し、これらのサブ問題の解決策を保存することです。大規模なサブ問題を解決する際に、これらのサブ問題のソリューションを将来使用する必要がある場合は、これらの計算されたソリューションを直接抽出して、繰り返しの操作を避けることができます。サブ問題を保存するためのソリューションは、配列での保存など、フォームメソッドを使用して記入できます。
実用的な例を使用して、動的プログラミングのアルゴリズムのアイデア - コインの変化の問題を反映してください。
質問の説明：
いくつかのコインがあり、無制限の量があるとします。一定数の変更を構成できるコインの最小数を見つけてください。たとえば、いくつかのタイプのコインは[1、3、5]、額面2のコインの最小数は2（1、1）、額面4のコインの最小数は2（1、3）、額面11のコインの最小コイン数は3（5、5、1または5、3、3）です。
問題分析：
さまざまなコインセットがアレイコイン[0、...、n-1]であると仮定します。次に、額面Kのコインの最小数を見つけ、カウント関数とコインアレイコインがこの状態に合っています。
count（k）= min（count（k -coin [0]）、...、count（k -coin [n -1]）） + 1;
そして、前の式は、条件K -COIN [i]> = 0 && k -coin [i] <kが満たされている場合にのみ保持されます。
k-coin [i] <k、count（k）を計算する場合、count（i）（i < - [0、k-1]）を満たす必要があるため、ここではバックトラッキングの問題が含まれます。
したがって、マトリックスマトリックス[k + 1] [coin.length + 1]を作成できるため、マトリックス[0] [j]はすべて0値に初期化され、マトリックス[i] [i] [coin.length]の額面のコインの最小コインを節約できます。
特定のプロセスは次のとおりです。
* k | Coin 1 3 5 min * 0 0 0 0 0 0 * 1 1 0 0 1 * 2 2 0 2 * 3 3 1 0 3、1 * 4 2 0 2、2 * 5 3 3 1 3、3、1 * 6 2 2 2 2、2、2 * ...
最後に、特定のJavaコードの実装は次のとおりです。
public static int backtrackingcoin（int [] coins、int k）{//バックトラッキングメソッド +動的プログラミングif（coins == null || coins.length == 0 || k <1）{return 0; } int [] [] matrix = new int [k + 1] [coins.length + 1]; for（int i = 1; i <= k; i ++）{for（int j = 0; j <coins.length; j ++）{int prek = i -coins [j]; （prek> -1）{// 0以上の場合にのみ、prekが配列マトリックスに存在し、バックトラッキングを実行できます。マトリックス[i] [j] = matrix [prek] [coins.length] + 1; //額面Iはバックトラッキングです。マトリックス[i] [coins.length] = matrix [i] [j]; }}} return matrix [k] [coins.length]; }コードがテストされており、質問によって与えられたすべてのテストケースが渡されました！
要約します
上記は、Javaダイナミックプログラミングのコイン変更問題実装コードに関するこの記事の全体的な内容です。私はそれが誰にでも役立つことを願っています。興味のある友人は、このサイトの他の関連トピックを引き続き参照できます。欠点がある場合は、それを指摘するためにメッセージを残してください。このサイトへのご支援をありがとうございました！