重庆网站建设定制,专业设计vi公司,个人申请微信小程序收费吗,怎么做360网站322. 零钱兑换
题目#xff1a;
给一个不同数额硬币的数组和一个目标金额#xff0c;硬币可取无限次#xff0c;求用硬币达到总金额的最小硬币数量。#xff08;求不同组合数/排列数#xff0c;但是硬币数量最小#xff09;
思路#xff1a;
求硬币数量最小#x…322. 零钱兑换
题目
给一个不同数额硬币的数组和一个目标金额硬币可取无限次求用硬币达到总金额的最小硬币数量。求不同组合数/排列数但是硬币数量最小
思路
求硬币数量最小与组合数/排列数无关所以遍历顺序正序倒序均可。
dp[j]含义 dp[j]凑成总金额j的最小硬币数量为dp[j]
递推公式 目标金额为j-coin[i]的最小硬币数量为dp[j-coin[i]]所以dp[j] dp[j-coin[i]]1。考虑加不加1
硬币数量无论无论多大数量都是1
初始化: dp[0]0目标金额为0那么对应的最少硬币总数为0因为有1存在所以不影响初始化启动
遍历顺序
与组合数/排列数无关倒序正序均可这里正序先物品硬币后背包目标金额。
总代码
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;//总额不超过力扣上线INT_MAXreturn dp[amount];}
};
279.完全平方数
题目
给一个不同完全平方的数组和一个目标总和不同完全平方数可取无限次求用完全平方数达到目标总和的最小完全平方的数量。求不同组合数/排列数但是所用完全平方的数量最小
完全平方数是另一个正整数的平方比如149是。1130不是。
思路
求达到目标总和的数量最小与组合数/排列数无关所以遍历顺序正序倒序均可。与上面一道题一模一样的..
dp[j]含义
dp[j]达到目标总和j的最小完全平方数的数量为dp[j]
递推公式
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]);
初始化:
dp[0]0虽然0可以解释为0*0有一种但是从递推公式可以看出
dp[j] min(dp[j - i * i] 1, dp[j]);是一直在选最小值的如果dp[0]等于0那后续值都会被0覆盖而0则因为完全平方数里有 1 的存在可以凑成任意总和不可能拼凑数是0所以为了这个目的dp[0]0
遍历顺序
与组合数/排列数无关倒序正序均可这里正序先物品完全平方数后背包目标总和。
总代码
// 版本一
class Solution {
public:int numSquares(int n) {vectorint dp(n 1, INT_MAX);dp[0] 0;for (int i 0; i n; i) { // 遍历背包for (int j 1; j * j i; j) { // 遍历物品dp[i] min(dp[i - j * j] 1, dp[i]);}}return dp[n];}
};
