Coin Change は、コイン (C[0]、C[1]...C[K-1]) を使用して N セントの合計を得る方法がいくつあるかを尋ねる非常に人気のある問題です。DP ソリューションは、メソッド s(N, K) = s(N, K-1) + s(NC[K-1], K) を使用することです。ここで、s(N,K) は到着する方法の量です。最初の K コイン (昇順でソート) の合計 N で。これは、最初の K コインを使用して N セントを稼ぐ方法の量は、K 番目のコインを使用せずに同じ金額に到達する方法の量の合計に、N-K 番目のコインに到達する方法の量を加えたものであることを意味します。どうすればこの解決策にたどり着くことができるのか、またそれが論理的にどのように理にかなっているのか、私には本当にわかりません。誰か説明してくれませんか？
1 に答える
3
DP を解くときに最も重要なことは、問題をより単純な部分問題のセットに減らすことです。ほとんどの場合、「単純」とは引数が小さいことを意味し、この場合、合計が少ないか残りのコインの値が少ない場合、問題はより単純になります。
問題を解決するための私の考え方は次のとおりです。コインのセットがあり、特定の合計を形成できる方法の数を数える必要があります。複雑に聞こえるかもしれませんが、コインが 1 枚少ないと少し楽になります。
ボトムケースを考えるのにも役立ちます。この場合、1 枚のコインしか持っていない場合、与えられた合計を形成できる方法がいくつあるかがわかります。これはどういうわけか、より単純な問題への還元がおそらく異なるコインの数を減らすことを示唆しています.
于 2014-07-16T09:01:02.520 に答える