/*****动态规划：DP方程：DP[i]中i表示当前兑换的面额，DP[i]为当前面额最少需要的硬币数DP[i]的初始值为INT_MAX-1;DP[coins[j]]的初始值为1;DP状态转移方程为：    for i:[1,amount]        for j:[0,len)            if(i>coins[j]) DP[i]=min(DP[i],DP[i-coins[j]]+1);            最终结果为DP[amount]如果DP[amount]==INT_MAX-1那么表示没有兑换成功，返回-1；****/class Solution {public:    int coinChange(vector
     
      & coins, int amount) {        if(amount==0) return 0;        if(coins.size()==0) return -1;        int len=coins.size();        vector
      
        DP(amount+1,amount+1);        DP[0]=0;        for(int i=1;i<=amount;i++){            for(int j=0;j
       
        =0) DP[i]=min(DP[i],1+DP[i-coins[j]]);            }        }        return DP[amount]>amount?-1:DP[amount];    }};
       
      
     

 

---

 

动态规划：O(n*amount)时间复杂度,O(amount)空间复杂度，可以类比为coins[j] step上楼梯，最终为上到amont

/*****动态规划：DP方程：DP[i]中i表示当前兑换的面额，DP[i]为当前面额最少需要的硬币数DP[i]的初始值为INT_MAX-1;DP[coins[j]]的初始值为1;DP状态转移方程为：    for i:[1,amount]        for j:[0,len)            if(i>coins[j]) DP[i]=min(DP[i],DP[i-coins[j]]+1);            最终结果为DP[amount]如果DP[amount]==INT_MAX-1那么表示没有兑换成功，返回-1；****/class Solution {public:    int coinChange(vector
     
      & coins, int amount) {        int len=coins.size();        //边界：amount和len分别为0的情况；        if(amount==0) return 0;        if(len==0) return -1+2*(int)(amount==0);                //amount和len都不为0的情况        vector
      
        DP(amount+1,INT_MAX-1);        for(int i=0;i
       
        0)                    DP[i]=min(DP[i],DP[i-coins[j]]+1);            }        }        if(DP[amount]==INT_MAX-1)            return -1;        else            return DP[amount];    }};