@ 代码随想录算法训练营第8周（C语言）|Day50（动态规划）

Day41、动态规划（包含题目 ● 322. 零钱兑换 ● 279.完全平方数）

322. 零钱兑换

题目描述

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

题目解答

int coinChange(int* coins, int coinsSize, int amount){//dp[j]表示凑成金额为j的硬币最少数量int dp[amount+1];//由于是求凑成金额所需最少的硬笔数量,应初始化为INT_MAXfor(int i=0;i<=amount;i++)dp[i]=INT_MAX;//base case dp[0]=0;for(int i=0;i<coinsSize;i++){for(int j=coins[i];j<=amount;j++){//dp[j-coins[i]]凑不成，其值为INT_MAX直接跳过if(dp[j-coins[i]]!=INT_MAX)dp[j]=fmin(dp[j],dp[j-coins[i]]+1);}}//如果未能凑成则返回-1return dp[amount]==INT_MAX?-1:dp[amount];
}

题目总结

最小完全背包问题。

279.完全平方数

题目描述

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

给你一个整数 n ，返回和为 n 的完全平方数的最少数量。

完全平方数是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

题目解答

int numSquares(int n) {int i;for(i=1;i<=n;i++){if((i*i)>n){break;}}int nums[i];for(int j=0;j<i;j++){nums[j]=j*j;}int dp[n+1];for(int j=0;j<=n;j++){dp[j]=INT_MAX;}dp[0]=0;for(int k=1;k<i;k++){for(int j=nums[k];j<=n;j++){if(dp[j-nums[k]]!=INT_MAX){dp[j]=dp[j]<dp[j-nums[k]]+1?dp[j]:dp[j-nums[k]]+1;}}}return dp[n];
}