力扣---零钱兑换---动态规划

思路：

 这是一道典型的动态规划问题（希望下次不用提示，能直接认出来）：我将g[i]定义为总金币为i所需的最少硬币个数。所以递推公式可以表示为：g[i]=min(g[i-1],g[i-2],g[i-5])+1，也就是g[i]=min(g[i-coins[j])+1。数组初始化就是g[0]=0，g[coins[j]]=1。需要注意的是：

coins[i]的最大值是INT_MAX,所以我更习惯用LONG_MAX为g赋初值。其次，因为无法开很大的数组，同时注意到coins[i]>amount的部分是没有意义的，所以只需要开amount大的数组即可。

代码：

C++：

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<long> g(10010,LONG_MAX);
        int len=coins.size();
        //初始化
        g[0]=0;
        for(int i=0;i<len;i++){
            if(coins[i]>amount){continue;}
            else{g[coins[i]]=1;}
        }
        //dp   g[i]=min(g[i-coins[j]])+1
        for(int i=1;i<amount+1;i++){
            for(int j=0;j<len;j++){
                if(i-coins[j]>=0 && g[i-coins[j]]!=LONG_MAX){
                    g[i]=min(g[i],g[i-coins[j]]+1);
                }
            }
        }
        if(g[amount]==LONG_MAX){
            return -1;
        }
        else{return g[amount];}
    }
};

Python：

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        g=[float("inf")]*10010
        len_coins=len(coins)
 
        g[0]=0
        for i in range(len_coins):
            if coins[i]>amount:
                continue
            else:
                g[coins[i]]=1
        for i in range(1,amount+1):
            for j in range(len_coins):
                if i-coins[j]>=0 and g[i-coins[j]]!=float("inf"):
                    g[i]=min(g[i],g[i-coins[j]]+1)
        if g[amount]==float("inf"):
            return -1
        else:
            return g[amount]

明天将更新力扣---最长有小括号