recursion - コインチェンジDPで同じコインを再利用できないのはなぜですか?

Question

例：

20$ が与えられた場合、20$ をコインと交換する WAYS を数えたい = { 5$,10$, 15$} コインの順序は関係ありません。

ここで解決

解決策は次のとおりです: 方法の総数 = コインを使用する + コインを使用しない : total_ways = count( S, m - 1, n ) + count( S, m, nS[m-1] )

木の形で：

Answer 1

解決策は次のとおりです: 方法の総数 = コインを使用する + コインを使用しない : total_ways = count( S, m - 1, n ) + count( S, m, nS[m-1] )

ソリューションステートメントを少し誤解していると思います。

正確には次のとおりです。

1) Optimal Substructure
To count total number solutions, we can divide all set solutions in two sets.
1) Solutions that do not contain mth coin (or Sm).
2) Solutions that contain at least one Sm.

これは、問題を同じ問題の 2 つの小さいバージョンに分割する方法です。

コインを使用せずに実行できる方法の数は、同じ目標の合計とより小さなコインのセットで同じ問題を実行します。

しかし、このコインの少なくとも1 つで実行できる方法の数は、コインのサイズによって削減された目標の合計と同じ問題ですが、許可されたコインのセットは同じです。

この 2 番目のセットでは、実際に同じコインを再度使用できます。