网站地图怎么做的,安徽元鼎建设工程网站,坪山附近公司做网站建设哪家技术好,wordpress字段管理爬楼梯 #xff08;进阶#xff09;
题目链接 爬楼梯#xff08;进阶版#xff09;
本题目属于排列中的背包问题#xff0c;所以先遍历背包#xff0c;后遍历物品#xff0c;剩下的就是完全背包的板子了#xff0c;下面直接上代码#xff1a;
#includeiostream…爬楼梯 进阶
题目链接 爬楼梯进阶版
本题目属于排列中的背包问题所以先遍历背包后遍历物品剩下的就是完全背包的板子了下面直接上代码
#includeiostream
#includevector
using namespace std;
int main (){int n,m;cinnm;vectorint dp(n1,0);dp[0] 1;for(int i1;in;i){for(int j1;jm;j){if(ij){dp[i] dp[i-j];}}}coutdp[n];return 0;
}
Leetcode 322. 零钱兑换
题目链接 322 零钱兑换
组合类注意一下初始化代码
class Solution {
public:int coinChange(vectorint coins, int amount) {vectorint dp(amount1,INT_MAX);dp[0] 0;for(int i0;icoins.size();i){for(int jcoins[i];jamount;j){if(dp[j-coins[i]] ! INT_MAX){dp[j] min(dp[j],dp[j-coins[i]]1);}}}if(dp[amount] INT_MAX){//没有被覆盖说明无法凑成amountreturn -1;}return dp[amount];}
};
Leetcode 279. 完全平方数
题目链接 279 完全平方数
只不过是把顺序数改成了平方数思路一样的完全平方数就是物品可以无限件使用凑个正整数n就是背包问凑满这个背包最少有多少物品直接上代码
class Solution {
public:int numSquares(int n) {vectorint dp(n1,INT_MAX);dp[0] 0;for(int i1;i*in;i){for(int ji*i;jn;j){dp[j] min(dp[j],dp[j-i*i]1);}}return dp[n];}
};
end
