网站建设报告心得体会,网页的制作方法,公众号的文章下载 wordpress,吐鲁番大型网站建设平台代码随想录第48天| 动态规划7 322. 零钱兑换279.完全平方数 322. 零钱兑换 LeetCode题目#xff1a; 322. 零钱兑换 代码随想录#xff1a;322. 零钱兑换 给你一个整数数组 coins #xff0c;表示不同面额的硬币#xff1b;以及一个整数 amount #xff0c;表示总金额。 计… 代码随想录第48天| 动态规划7 322. 零钱兑换279.完全平方数 322. 零钱兑换 LeetCode题目 322. 零钱兑换 代码随想录322. 零钱兑换 给你一个整数数组 coins 表示不同面额的硬币以及一个整数 amount 表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额返回 -1 。 你可以认为每种硬币的数量是无限的。 dp[j] min(dp[j - coins[i]], do[j] ) dp[0] 0; 其他取最大的INT_MAX 因为是求数量最小值背包和物品顺序无所谓
class Solution {
public:int coinChange(vectorint coins, int amount) {vectorint dp(amount 1, INT_MAX);dp[0] 0;for(int i 0; i coins.size(); i){ // 先物品for(int j coins[i]; j amount; j){if (dp[j - coins[i]] ! INT_MAX) { // 如果dp[j - coins[i]]是初始值则跳过dp[j] min(dp[j - coins[i]] 1, dp[j]);}}}if(dp[amount] INT_MAX) return -1;return dp[amount];}
};时间复杂度: O(n * amount)其中 n 为 coins 的长度 空间复杂度: O(amount)
279.完全平方数 LeetCode题目279.完全平方数 代码随想录279.完全平方数 给你一个整数 n 返回 和为 n 的完全平方数的最少数量 。 完全平方数 是一个整数其值等于另一个整数的平方换句话说其值等于一个整数自乘的积。例如1、4、9 和 16 都是完全平方数而 3 和 11 不是。 1.含义dp[j]和为j的完全平方数的最少数量为dp[j] 2.dp[j] 可以由dp[j - i * i]推出 dp[j - i * i] 1 便可以凑成dp[j]。 此时我们要选择最小的dp[j]所以递推公式dp[j] min(dp[j - i * i] 1, dp[j]);
class Solution {
public:int numSquares(int n) {// 完全背包求装满背包的物品的最小数量vectorint dp(n 1, INT_MAX);dp[0] 0;for(int i 1; i * i n; i){ //先物品for(int j i * i; j n; j){dp[j] min(dp[j-i*i] 1, dp[j]);}}return dp[n];}
};
