【算法】动态规划

为了减少重复的递归调用，我们可以反过来计算。先计算f(2)，有了f(2)再计算f(3)，以此类推，计算到f(n)。在此过程中不需要任何递归

• 先找出一分钱的找零方法，把最小硬币数存入coinUsed[1] 依次找出2分钱、3分钱…的找零方法，直到到达要找零的钱为止：
• 对每个要找的零钱i，可以把i分解成某个coins[j]和 i - coins[j]， 所需硬币数为coinUsed[i-coins[j]]+1。
• 对所有的j，取最小的coinUsed[i-coins[j]]+1作为i元钱找零的的答案。

  void makechange( int coins[ ],  int differentCoins, 
                      int maxChange, int coinUsed[] )
  { coinUsed[0] = 0; 
    for (int cents = 1; cents <= maxChange; cents++) { //cents为待找零的零钱数额，从1分到所求的maxChange分
           int minCoins = cents; 
           for (int j = 1; j < differentCoins; j++)
                 { if (coins[j] > cents) continue; 
                   if (coinUsed[ cents - coins[j] ] + 1 < minCoins) 
                      minCoins = coinUsed[ cents - coins[j] ] + 1;
                }
           coinUsed[cents] = minCoins; 
  //Coins存放所有不同的硬币值，不同的硬币个数为differentCoins。
       }
  }