DP硬幣找零說明

Question

硬幣找零是一個非常流行的問題，詢問你有多少種方法得到的使用硬幣ñ美分總和（C [0]，C [1] ... C [K-1]） 。 DP解決方案是使用方法 s（N，K）= s（N，K-1）+ s（NC [K-1]，K），其中s（N，K）用第一K個硬幣到達總數N（按升序排列）。 這意味着使用第一個K硬幣賺取N美分的方法的數量是在不使用第K個硬幣添加到達到第N個硬幣的方式的數量的情況下達到相同總和的方式的總和。我真的不明白你如何能夠遇到這個解決方案，以及它是如何合理地進行邏輯的。有人可以解釋嗎？

Answer 1

解決一個DP時，最重要的是把問題縮小到一組簡單的子問題。大部分時間「簡單」意味着參數較小，在這種情況下，如果總和較小或剩餘硬幣值較小，則問題更簡單。

我的思維來解決這個問題的方法是：好吧，我有一組硬幣的，我需要計算的方法，我可以形成一個給定的款項數目。這聽起來很複雜，但如果我少了一枚硬幣，它會容易一些。

這也有助於思考最底層的情況。在這種情況下，如果你只有一枚硬幣，你就知道你可以用多少種方式組成一筆給定的金額。這不知何故表明，簡化問題的減少可能會減少不同硬幣的數量。