云盘网站建设,cnnic网站备案,缪斯设计上海,怎么制作网页视频教学70.爬楼梯#xff08;进阶#xff09;
分析#xff1a;基本动态规划转换为完全背包#xff0c;因为1、2 两种上楼梯方式是无限选择的
思路#xff1a;
1. j 表示 容量为 j 时#xff0c;装满有dp[j]种方法2. dp[j]dp[j-nums[i]]3. 初始化 dp[0]1,dp[1]14. 遍历顺序进阶
分析基本动态规划转换为完全背包因为1、2 两种上楼梯方式是无限选择的
思路
1. j 表示 容量为 j 时装满有dp[j]种方法2. dp[j]dp[j-nums[i]]3. 初始化 dp[0]1,dp[1]14. 遍历顺序外层遍历容量 内层遍历物品
class Solution {
public:int climbStairs(int n) {vectorintdp(n1,0);dp[0]dp[1]1;for(int i2;in;i){for(int j1;j2;j){dp[i]dp[i-j];}}return dp[n];}
}; 322.零钱兑换
分析硬币无限组合成金额 - 完全背包组合
思路
1.dp存储金额为 j 时有 dp[j] 种方法2.dp[j]min(dp[j],dp[j-coins[i]]1)3.dp[0]04.遍历顺序外层遍历硬币内层遍历容量
class Solution {
public:int coinChange(vectorint coins, int amount) {vectorintdp(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) return -1;return dp[amount];}
}; 279.完全平方数
思路 1.dp存储 容量为 j 时装满的最少使用数字为dp[j]种方法 2.dp[j]min(dp[j],dp[j-i*i]1) 3.初始化dp[0]0 INT_MAX 4.遍历顺序外层遍历数字内层遍历容量
class Solution {
public:int numSquares(int n) {vectorintdp(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];}
};
