北京好的做网站的公司,wordpress 去掉版权信息,网站域名要钱吗,如何确定网站栏目思路#xff1a; 这是一道典型的动态规划问题#xff08;希望下次不用提示#xff0c;能直接认出来#xff09;#xff1a;我将g[i]定义为总金币为i所需的最少硬币个数。所以递推公式可以表示为#xff1a;g[i]min(g[i-1],g[i-2],g[i-5])1#xff0c;也就是g[i]min(g[i-…
思路 这是一道典型的动态规划问题希望下次不用提示能直接认出来我将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]0g[coins[j]]1。需要注意的是 coins[i]的最大值是INT_MAX,所以我更习惯用LONG_MAX为g赋初值。其次因为无法开很大的数组同时注意到coins[i]amount的部分是没有意义的所以只需要开amount大的数组即可。 代码
C
class Solution {
public:int coinChange(vectorint coins, int amount) {vectorlong g(10010,LONG_MAX);int lencoins.size();//初始化g[0]0;for(int i0;ilen;i){if(coins[i]amount){continue;}else{g[coins[i]]1;}}//dp g[i]min(g[i-coins[j]])1for(int i1;iamount1;i){for(int j0;jlen;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)]*10010len_coinslen(coins)g[0]0for i in range(len_coins):if coins[i]amount:continueelse:g[coins[i]]1for i in range(1,amount1):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 -1else:return g[amount]
明天将更新力扣---最长有小括号
