本文共 1207 字，大约阅读时间需要 4 分钟。

硬币找零问题，我们在贪心算法那一节中讲过一次。我们今天来看一个新的硬币找零问题。假设我们有几种不同币值的硬币 v1，v2，……，vn（单位是元）。如果我们要支付 w 元，求最少需要多少个硬币。比如，我们有 3 种不同的硬币，1 元、3 元、5 元，我们要支付 9 元，最少需要 3 个硬币（3 个 3 元的硬币）。

思路分析：

• 非常简单的动态规划表，统计在上一次情况的基础上，加上一枚1或3或5金额硬币之后的情况。如果该行有等于money的情况，返回即可（说明加到本轮，已经可以满足）。
  
• 代码实现

// Example program#include 
   
    #include 
    
     using namespace std;int minCoins(int money){
       if (money == 1 || money == 3 || money == 5)        return 1;    vector
     
      
       > state(money);    for (auto &row : state)        row.resize(money + 1);    if (money >= 1)        state[0][1] = true;    if (money >= 3)        state[0][3] = true;    if (money >= 5)        state[0][5] = true;    for (int i = 1; i < money; i++)    {
           for (int j = 1; j <= money; j++)        {
               if (state[i - 1][j])            {
                   if (j + 1 <= money)                    state[i][j + 1] = true;                if (j + 3 <= money)                    state[i][j + 3] = true;                if (j + 5 <= money)                    state[i][j + 5] = true;                if (state[i][money])                    return i + 1;            }        }    }    return money;}int main(){
       cout << minCoins(9) << endl;    return 0;}
      
     
    
   

转载地址：http://recii.baihongyu.com/