recursion - 簡単な動的計画法の再帰式 (uva 147 コインの変更)

Question

問題は硬貨の両替についてです - 「5c,10c を持っている場合、3,5,10 ドルを何回両替できるか......

" http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=83

問題はさまざまなブログで何度も解決されています（解決策 はこちら）

dpで一番難しいのは、部分問題間の関係を理解し​​、式（最適部分構造）を求めることです。

ソリューションのように、方法を 2d テーブルに格納する実際の for ループのみを示します。

for (int i = 2; i <= NCHANGES; ++i){
for (int m = 1; m <= MAX_AMOUNT; ++m){
  if (m >= coins[i])
    n[i][m] = n[i-1][m] + n[i][m - coins[i]];
  else
    n[i][m] = n[i-1][m];
}

}

=================================

実際の重要なコード:

  if (m >= coins[i])
        n[i][m] = n[i-1][m] + n[i][m - coins[i]];
      else
        n[i][m] = n[i-1][m];

私の考え。

例: (それ以外の場合)

• 使用する金額は 5 セントで、1 コインは 5c です。方法は 1 つだけです: 5c = 1 * 5c (store n[5][coin(5)])

• 使用するコインは 5c と 2 枚あります: 5c と 10c 5c と 10c の 両方を使用することはできません => 1 つの方法に戻ります (n[5][coin(5, 10)]) この場合

だから n[i][m] = n[i-1][m]

最初のifケースを説明できますか? n[i][m] = n[i-1][m] + n[i][m - コイン[i]] ?