英文网站首页优化,asp 网站建设教程,义乌网站建设公司排名,上海网站建设seo18881 70. 爬楼梯#xff08;完全背包版#xff09;
70. 爬楼梯
完全背包装满的选法排列的套路#xff0c;AC代码#xff1a;
class Solution {
public:/*完全背包的思路:1 2是两个物体 可以无限取*/int dp[50]; // 能爬到第i楼的选法的排列数/*dp[j] dp[j - i];dp[0] 1fo…1 70. 爬楼梯完全背包版
70. 爬楼梯
完全背包装满的选法排列的套路AC代码
class Solution {
public:/*完全背包的思路:1 2是两个物体 可以无限取*/int dp[50]; // 能爬到第i楼的选法的排列数/*dp[j] dp[j - i];dp[0] 1for容积j for物体i 排列无限个模拟——n3*/int climbStairs(int n) {dp[0] 1;for(int j 0; j n; j)for(int i 1; i 2; i) //物体if(j i)dp[j] dp[j - i];// for(int i 1; i 2; i)// {// for(int j 0; j n; j)// cout tmp[i][j] ;// puts();// }return dp[n];}
};
2 322. 零钱兑换
322. 零钱兑换
之前做过直接看这篇 3 279. 完全平方数
279. 完全平方数
之前没学多重背包之前看到题目是蒙的现在学完时候很自然就做出来了AC代码
class Solution {
public:int dp[10010]; // dp[1]表示 凑成i的完全平方数最少需要的数目/*转成完全背包物品i 1....sqrt(n)背包ndp[j] min(dp[j- i]1,dp[j])装i 不撞idp[0] 0 其他非0下标全设为INT_MAXij模拟——*/int numSquares(int n) {dp[0] 0;for(int j 1; j n; j)dp[j] INT_MAX;for(int i 1; i*i n; i){for(int j 0; j n; j){if(j i*i)dp[j] min(dp[j- i*i]1,dp[j]);else dp[j] dp[j];}// for(int j 0; j n; j) cout dp[j] ;// puts();}return dp[n];}
};
