江苏天目建设网站,已有网站域名 怎么做网站,建设银行反钓鱼网站,云支付 wordpress 免签代码随想录刷题60Day 目录
前言
零钱兑换 完全平方数 前言
今天重点是对完全背包问题进一步了解#xff0c;难度不大#xff0c;重点是区分与其他背包问题在初始和遍历上的一些细节。 零钱兑换 int coinChange(vectorint coins, int amount) {if (!amount)re…代码随想录刷题60Day 目录
前言
零钱兑换 完全平方数 前言
今天重点是对完全背包问题进一步了解难度不大重点是区分与其他背包问题在初始和遍历上的一些细节。 零钱兑换 int coinChange(vectorint coins, int amount) {if (!amount)return 0;const int size coins.size();vectorint 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) {vectorint 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];}
