找硬币

题目描述

如果我们有面值1元，3元和5元的硬币若干，如何用最少的硬币凑够11元？

1. 如何用最少的硬币凑够i元？

当 i = 0 时，显然需要0个硬币。

这里我们使用 d(i) = j 来描述，于是我们有 d(0) = 0。
当 i = 1 时，只有1元硬币可用，当我使用1个1元硬币，在去求解如果 i = 0这个问题，前面已经球得这个问题的解为0，所以i=1时这个问题求解结束，得到取1个1元硬币这个解，所以d(1) = 1。
当 i = 2 时， 可以使用2个1元硬币，这个过程首先，取1个1元硬币，然后去求解i=1这个问题，上面已经有了这个问题的解答，所以这个问题求解结束，这种情况需要2个1元硬币。还有一种情况去一个2元硬币，然后去求解i = 0这个问题，上面也已经有了解答，所以这种情况下，需要1个2元硬币。因为问题是要求硬币数最少，所以去上面两种情况中，结果较小的1个作为结果，即min{1+d(1),1+d(0)},所以结果为d(2) = 1。
当 i = 3 时，我们用按照上述方式求解，过程的公式化为1) d(3) = min{1+d(3-1),1+d(3-3)} = min{1+d(2),1+d(1),1+d(0)} = min{2,2,1} = 1
由以上的的过程我们可以得到两个非常重要的概念，状态和状态转移方程。上文中d(i)表示凑够i元需要的最少硬币数，我们将它定义为状态。我们根据子问题来找到状态的描述。最终我们求解的问题，可以用这个状态来表示，即d(11)。那什么是状态转移方程呢？,既然我们用d(i)表示状态，那么状态转移方程自然包含d(i)，上文中包含d(i)的方程是d(3) = min{1+d(3-1),1+d(3-3)}，没错，他就是状态转移方程，描述状态之间是如何转移的。这里我们对它一般化d(i) = min{d(i-vj)+1} 其中i-vj >=0，vj表示第j个硬币的面值。 j = 1,2,3 vj = 1 , 3, 5。
下面是解题的代码

 vector<int> coins{1,3,5};
 int coinChange(vector<int>& coins, int amount) {
      vector<int> dp;
      for (int i=0;i<=amount;i++) {
               dp.push_back(9999);
      }
     dp[0] =0;
     for (int i = 1;i<=amount;i++)
          for (int j = 0;j < coins.size();j++)
                if ((i-coins[j] >= 0)&&(dp[i]>dp[i-coins[j]]+1)) 
                         dp[i] = dp[i-coins[j]]+1;
                

     if (dp[amount] == 9999)
         return -1;
     else 
         return dp[amount];
    }