力扣刷题记录106.1-----322. 零钱兑换

---

一、题目

二、代码

class Solution
{
public:
    //dp[j] 表示总金额为j   所需要的最小硬币数目
    //完全背包  可重用
    int coinChange(vector<int>& coins, int amount) 
    {
       int i,j;
       int return_int=-1;
       vector<int> dp(amount+1,INT32_MAX);
       dp[0]=0;
       for(i=0;i<coins.size();i++)
       {
           for(j=coins[i];j<=amount;j++)
           {
                if(INT32_MAX-dp[j-coins[i]]>=1)
                dp[j]=min(dp[j],dp[j-coins[i]]+1);
                //  std::cout<<"i  "<
                //  std::cout<<"dp[i]  "<
                //  std::cout<<"dp[j-coins[i]]+1  "<
           }
       }

      if(dp[amount]==INT32_MAX)
      {
        std::cout<<"未被初始化   "<<std::endl; 
         return_int=-1;
      } 
      else return_int=dp[amount];

    //   for(i=0;i
       return return_int;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

三、运行结果