旅游后台网站,百度一下下载安装,维度 网站建设,移动商城网站建设 深圳目录
一、#xff08;leetcode 70#xff09;爬楼梯
二、#xff08;leetcode 322#xff09;零钱兑换
三、#xff08;leetcode 279#xff09;完全平方数 一、#xff08;leetcode 70#xff09;爬楼梯
力扣题目链接 状态#xff1a;查看思路后AC 除…目录
一、leetcode 70爬楼梯
二、leetcode 322零钱兑换
三、leetcode 279完全平方数 一、leetcode 70爬楼梯
力扣题目链接 状态查看思路后AC 除了常规的可以爬一或二级台阶当题目稍微修改一下变成可以爬m级台阶之前的DP思路就有局限dp[i] dp[i-1] dp[i-2为了通杀这类问题可以将题目转换为完全背包问题可以爬的楼梯级数就是背包中的物品楼梯总数就是背包注意例如五级台阶122和221是不同的方法所以类比昨天的组合总数问题需要先遍历背包再遍历物品、
class Solution {
public:int climbStairs(int n) {// 转换为完全背包问题vectorint dp(n1, 0);dp[0] 1;for(int i 1; i n; i){ // 先背包for(int j 1; j 2; j){ // 后物品可以爬的台阶数题目中是2if(i-j 0) dp[i] dp[i-j];}}return dp[n];}
};
二、leetcode 322零钱兑换
力扣题目链接 状态查看思路Debug后AC。 class Solution {
public:int coinChange(vectorint coins, int amount) {vectorint dp(amount1, INT_MAX);dp[0] 0;int len coins.size();for(int i 0; i len; i){for(int j coins[i]; j amount; 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];}
};
三、leetcode 279完全平方数
力扣题目链接 状态查看思路Debug后AC。 注意转换为完全背包后的先物品再背包和先背包再物品的遍历方式在实现上的细节问题这里将两种代码都放上。
先物品再背包
class Solution {
public:int numSquares(int n) {// 完全平方数就是物品总和就是背包转换成一个无重复组合的完全背包问题vectorint dp(n1, INT_MAX);dp[0] 0;for(int i 1; i*i n; i){// 先物品for(int j i*i; j n; j){dp[j] min(dp[j], dp[j - i*i]1);}}return dp[n];}
};
先背包再物品
class Solution {
public:int numSquares(int n) {// 完全平方数就是物品总和就是背包转换成一个无重复组合的完全背包问题vectorint dp(n1, INT_MAX);dp[0] 0;for(int i 0; i n; i){// 先背包for(int j 1; j*j i; j){if(dp[i - j*j] ! INT_MAX){dp[i] min(dp[i], dp[i - j*j]1);}}}return dp[n];
