我的网站在百度搜不到,中国建筑网官网查询资质,做销售的什么网站好,贴吧引流推广题目1#xff1a;70 爬楼梯#xff08;进阶版#xff09;
题目链接#xff1a;爬楼梯
对题目的理解
需要爬n阶才能到达楼顶#xff0c;每次可以至多爬m个台阶#xff0c;m的区间是[1,n)#xff0c;有多少种方法爬到楼顶
本题是一个完全背包问题#xff0c;每一阶都…题目170 爬楼梯进阶版
题目链接爬楼梯
对题目的理解
需要爬n阶才能到达楼顶每次可以至多爬m个台阶m的区间是[1,n)有多少种方法爬到楼顶
本题是一个完全背包问题每一阶都可以重复使用例如跳了1阶还可以继续跳1阶1、2 步 和 2、1 步都是上三个台阶但是这两种方法不一样
1阶2阶.... m阶就是物品楼顶就是背包
问跳到楼顶有几种方法其实就是问装满背包有几种方法
动规五部曲
1dp数组及下标i的含义
dp[j]表示容量为j的背包的最大价值
本题的含义就是走到第j阶楼梯有几种走法最终求的是dp[n]
2递推公式
dp[j]dp[j-i] i代表本次走的阶梯数
3dp数组初始化
dp[0]1,因为递推公式是递加的如果初始化为0的话那么dp数组全为0初始化为1相当于初始化了根基其余下标为非零的dp[j]初始化为0因为递推公式是递加的关系所以初始化为0才能不掩盖求得的dp数组的值
4遍历顺序
因为本题求的是完全背包的排列问题所以需要先正序遍历背包后正序遍历物品这样才可以求得最终的排列
5打印dp数组
代码
#includeiostream
#includevector
using namespace std;
int main(){int n,m;cinnm;//定义并初始化dp数组vectorint dp(n1,0);dp[0]1;//递推,排列问题先正序遍历背包后正序遍历物品for(int j1;jn;j){for(int i1;im;i){if(ji) dp[j]dp[j-i];}}coutdp[n]endl;
}
时间复杂度: O(n * m)空间复杂度: O(n)
题目2322 零钱兑换
题目链接零钱兑换
对题目的理解
整数数组coins中的每个元素代表不同面额的硬币整数amount表示总金额
返回可以凑成总金额所需的最少的硬币数如果没有则-1其中每种硬币可无限次使用
硬币无限次使用说明这是典型的完全背包问题
动规五部曲
1dp数组及下标i的含义
装满容量为j的背包最少物品个数为dp[j] 最终要求dp[amount]
2递推公式
dp[j]min(dp[j],dp[j-coins[i]]1) 因为放入一个物品减去coins[i]但是个数要加1
3dp数组初始化
dp[0]0 测试用例已给出 对于非零下标 考虑到递推公式 本题因为求的是二者的最小值所以将dp[j]初始化为最大值INT_MAX这样递推式得到的值才不会被覆盖
4遍历顺序
本题求的是最小硬币数顺序颠不颠倒都无所谓所以先遍历物品还是先遍历背包都行
5打印dp数组
代码(先遍历物品后遍历背包)
class Solution {
public:int coinChange(vectorint coins, int amount) {//定义并初始化dp数组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) return -1;return dp[amount];}
};
时间复杂度: O(n * amount)其中 n 为 coins 的长度空间复杂度: O(amount)
代码先遍历背包后遍历物品
class Solution {
public:int coinChange(vectorint coins, int amount) {//定义并初始化dp数组vectorint dp(amount1,INT_MAX);dp[0]0;//递推for(int j0;jamount;j){for(int i0;icoins.size();i){if(jcoins[i] 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];}
};
时间复杂度: O(n * amount)其中 n 为 coins 的长度空间复杂度: O(amount)
题目3279 完全平方数
题目链接完全平方数
对题目的理解
返回和为n的完全平方数的最小数量其中完全平方数可以重复使用因此是一个完全背包问题
完全平方数是物品n是背包
任何一个数都可以凑成完全平方数的总和因为完全平方数有1
动规五部曲
1dp数组及下标i的含义
dp[j]:背包容量为j时完全平方数的最小数量是dp[j] 最终求的是dp[n]
2递推公式
我怎么表示完全平方数呢使用i*i
dp[j]min(dp[j-i*i]1,dp[j])
3dp数组初始化
dp[0]0 因为题目给的n至少是1根据递推公式dp[0]要从0开始这样才能继续向下推导而根据递推公式求得是二者的最小值所以将非零下标对应的dp[j]初始化为最大值INT_MAX
4遍历顺序
本题求的也是最少数量与顺序无关所以先遍历物品还是先遍历背包均可
5打印dp数组
代码(先遍历物品后遍历背包)
class Solution {
public:int numSquares(int n) {//定义并初始化dp数组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];//注意本题不像上一题有不存在的现象任何一个数都会由若干个完全平方数组成 }
};
时间复杂度: O(n * √n)空间复杂度: O(n)
代码先遍历背包后遍历物品
class Solution {
public:int numSquares(int n) {//定义并初始化dp数组vectorint dp(n1,INT_MAX);dp[0]0;//递推for(int j0;jn;j){for(int i1;i*in;i){if(ji*i) dp[j]min(dp[j],dp[j-i*i]1);}}return dp[n];//注意本题不像上一题有不存在的现象任何一个数都会由若干个完全平方数组成 }
};
时间复杂度: O(n * √n)空间复杂度: O(n)
