【算法日志】动态规划刷题：完全背包应用问题(day39)

代码随想录刷题60Day

---

目录

前言

零钱兑换

 完全平方数

---

前言

今天重点是对完全背包问题进一步了解，难度不大，重点是区分与其他背包问题在初始和遍历上的一些细节。

---

零钱兑换

int coinChange(vector<int>& coins, int amount) {if (!amount)return 0;const int size = coins.size();vector<int> dp(amount + 1, 0);sort(coins.begin(), coins.end());if (amount < coins[0])return -1;for (int i = 1; i <= amount; ++i){for (int j = size - 1; j >= 0; --j){if (i >= coins[j] && (!(i - coins[j]) || dp[i - coins[j]])){if (dp[i])dp[i] = min(dp[i], dp[i - coins[j]] + 1);elsedp[i] = dp[i - coins[j]] + 1;} }}if (dp[amount])return dp[amount];return -1;}

 完全平方数

	int numSquares(int n) {vector<int> dp(n + 1, 0);for (int i = 1; i <= n; ++i){for (int j = 1; j * j <= i; j++){if (dp[i])dp[i] = min(dp[i], dp[i - j * j] + 1);elsedp[i] = dp[i - j * j] + 1;}}return dp[n];}