代码随想录算法训练营第四十四天| LeetCode70. 爬楼梯 (进阶)、322. 零钱兑换、279.完全平方数

本文主要是介绍代码随想录算法训练营第四十四天| LeetCode70. 爬楼梯 (进阶)、322. 零钱兑换、279.完全平方数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一、LeetCode 70. 爬楼梯 (进阶)

题目链接/文章讲解/视频讲解:https://programmercarl.com/0070.%E7%88%AC%E6%A5%BC%E6%A2%AF%E5%AE%8C%E5%85%A8%E8%83%8C%E5%8C%85%E7%89%88%E6%9C%AC.html

状态:已解决

1.思路 

        这道题跟70.爬楼梯 - 力扣(LeetCode)很像,区别在于此题一次性能爬的台阶数不是固定的,而是题目给定的,因此就不能根据之前的递推式做了。

        那我们再来仔细看看这道题,题目给出了需要爬到的楼顶的阶数以及每次可爬的范围。那么这道题实质就是一道完全背包的题:背包容量为n,物品一共m个,且每个物品可以取无限次,问背包装入物品的排列一共有多少种。

        那么这道题就被转换成完全背包问题中的排序题了,跟前一天练的组合总和 Ⅳ-CSDN博客中的377题没有区别。

(1)确定dp数组以及下标含义:

        dp[j]: 爬到第 j 层楼梯,有dp[j]种方法。

(2)确定递推式:

        dp[i]有几种来源,dp[i - 1],dp[i - 2],dp[i - 3] 等等,即:dp[i - j]。那么递推公式为:dp[i] += dp[i - j]

(3)dp数组的初始化:

        既然递归公式是 dp[i] += dp[i - j],那么dp[0] 一定为1,dp[0]是递归中一切数值的基础所在,如果dp[0]是0的话,其他数值都是0了。

        下标非0的dp[i]初始化为0,因为dp[i]是靠dp[i-j]累计上来的,dp[i]本身为0这样才不会影响结果。

(4)确定遍历顺序:

        刚刚说了,这是一个求排列的方式,因此外层循环是容量,内层循环是物品。并且完全背包的两层循环都是从前往后遍历。

(5)举例推导dp数组:

        和刚刚的377题一致。

2.代码实现

#include<bits/stdc++.h>
using namespace std;
int main(void){int n,m;cin>>n>>m;vector<int> dp(n+1,0);dp[0] = 1;for(int j=0;j<=n;j++){for(int i=1;i<=m;i++){if(j >= i) dp[j] += dp[j-i];}}cout<<dp[n];return 0;
}

时间复杂度: O(n * m)

空间复杂度: O(n)

二、322. 零钱兑换

题目链接/文章讲解/视频讲解:https://programmercarl.com/0322.%E9%9B%B6%E9%92%B1%E5%85%91%E6%8D%A2.html

状态:已解决

1.思路 

        做过518. 零钱兑换 II - 力扣(LeetCode)的同学会觉得这两道题很像。确实很像,题目背景是相同的,区别在于518求的是凑钱的所有凑法,而322是求能够凑齐目标金额的最小硬币数。

(1)确定dp数组以及下标含义:

        dp[j]:凑足金额为 j 所需钱币的最少个数为dp[j]。

(2)确定递推公式:

        凑足总额为 j - coins[i] 的最少个数为dp[j - coins[i]],那么只需要加上一个钱币coins[i] 即dp[j - coins[i]] + 1就是dp[j](考虑coins[i]),因为dp[j] 要取所有 dp[j - coins[i]] + 1 中最小的,因此递推公式:dp[j] = min(dp[j - coins[i]] + 1, dp[j]);

(3)dp数组的初始化:

        首先凑齐金额为0所需的硬币数一定为0,那么其他非0下标呢?由递推公式dp[j] = min(dp[j - coins[i]] + 1, dp[j]);我们知道dp[j]是要与计算值求最小的,故为使计算值不被覆盖,初始值就应该为最大值,即:

vector<int> dp(amount+1,INT_MAX);
dp[0] = 0;

(4)确定遍历顺序:

        因为本题要求硬币的最少数量,而不是有多少种凑法,那么钱币有顺序和没有顺序都可以,都不影响钱币的最小个数。所以本题并不强调集合是组合还是排列。所以本题的两个for循环的关系是:外层for循环遍历物品,内层for遍历背包或者外层for遍历背包,内层for循环遍历物品都是可以的!

        按惯例做法,这里采用coins放在外循环,target在内循环的方式。本题钱币数量可以无限使用,那么是完全背包。故内循环是正序遍历。

(5)举例推导dp数组:

        dp[amount]为最终结果。

2.代码实现 

class Solution {
public:int coinChange(vector<int>& coins, int amount) {vector<int> dp(amount+1,INT_MAX);dp[0] = 0;for(int i=0;i<coins.size();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);}}//for(int i=0;i<=amount;i++) cout<<dp[i]<<" ";if(dp[amount] == INT_MAX) return -1;return dp[amount];}
};

时间复杂度:O(n * amount),n为coins长度

空间复杂度:O(amount) 

三、279.完全平方数

题目链接/文章讲解/视频讲解:https://programmercarl.com/0279.%E5%AE%8C%E5%85%A8%E5%B9%B3%E6%96%B9%E6%95%B0.html

状态:已解决

1.思路 

        换汤不换药,这道题跟上道题如出一辙:给一个容量为n的背包,求装满这个背包最少需要多少物品。物品是什么?就是一个平方数(同个数可以无限使用)。那物品的种类有多少个呢?肯定不超过sqrt(n)个!(sqrt(n)向上取整就是能够凑齐n的平方数的极限值 ),也就是说,上道题的nums[i]在这道题就是 i*i ,除此之外两道题就没有区别了。想清楚了这些,就可以开始写代码了。

(1)确定dp数组以及下标含义:

        dp[j]:和为j的完全平方数的最少数量为dp[j]。

(2)确定递推公式:

        凑足和为 j - i*i 的最少个数为dp[j - i*i],那么只需要加上一个平方数 i*i 即dp[ j - i*i ] + 1就是dp[j](考虑 i * i),因为dp[j] 要取所有 dp[j -i*i ] + 1 中最小的,因此递推公式:dp[j] = min(dp[j - i * i ] + 1, dp[j]);

(3)dp数组的初始化:

        根据题目描述,找到若干个完全平方数(比如 1, 4, 9, 16, ...),并没有从0开始,故给dp[0]=0。

        对于非0下标的dp[j],从递归公式dp[j] = min(dp[j - i * i] + 1, dp[j]) 中可以看出每次dp[j]都要选最小的,所以非0下标的dp[j]一定要初始为最大值,这样dp[j]在递推的时候才不会被初始值覆盖

(4)确定遍历顺序:

        和上题的分析是一致的

(5)举例推导dp数组:

        dp[n]为最终结果。

2.代码实现 

class Solution {
public:int numSquares(int n) {vector<int> dp(n+1,INT_MAX);dp[0] = 0;for(int i=1;i * i<=n;i++){for(int j=i*i;j<=n;j++){if(dp[j-i*i] != INT_MAX)dp[j] = min(dp[j],dp[j-i*i]+1);}}return dp[n];}
};

时间复杂度: O(n * √n)

空间复杂度: O(n)

这篇关于代码随想录算法训练营第四十四天| LeetCode70. 爬楼梯 (进阶)、322. 零钱兑换、279.完全平方数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/918989

相关文章

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门(一):登录与退出》 《Spring-Security-入门(二):基于数据库验证》 《Spring-Security-入门(三):密码加密》 《Spring-Security-入门(四):自定义-Filter》 《Spring-Security-入门(五):在 Sprin

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

Java进阶13讲__第12讲_1/2

多线程、线程池 1.  线程概念 1.1  什么是线程 1.2  线程的好处 2.   创建线程的三种方式 注意事项 2.1  继承Thread类 2.1.1 认识  2.1.2  编码实现  package cn.hdc.oop10.Thread;import org.slf4j.Logger;import org.slf4j.LoggerFactory

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

活用c4d官方开发文档查询代码

当你问AI助手比如豆包,如何用python禁止掉xpresso标签时候,它会提示到 这时候要用到两个东西。https://developers.maxon.net/论坛搜索和开发文档 比如这里我就在官方找到正确的id描述 然后我就把参数标签换过来

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n