70.爬楼梯（完全背包）1.代码classSolution{public:intclimbStairs(intn){vectornums;vectorf(n+1);f[0]=1;for(inti=0;i=j)f[i]+=f[i-j];}}returnf[n];}};2.递归五部曲1.确定dp数组和其下标的含义题目所求是爬到楼梯顶的方案数，f[i]就是爬到i层的方案数。f[n]就是爬到楼顶的方案数2.确定递推公式题目所求是方案数，如f[i]，方案数就是所有可以到达i的方案数相加，比如可以走1步和2步，f[i]=f[i-1]+f[i-2]+f[i-3]+......，所以遍历到这个物品时候，就可以
Leetcode70题有人问我：烤冷面你这两周怎么总搞简单题？我想说：一步一步来～题干简述给定：假设你正在爬楼梯，需要爬n阶你才能到达楼顶。每次你可以爬1或2个台阶。要求：计算出有多少种爬楼梯的方式。解题思路如果我们缩小视野（把大问题化为小问题），爬到第n阶台阶有两种方式：从n-1阶爬一级台阶从n-2阶爬两级台阶用公式表达：dp[n]=dp[n−1]+dp[n−2]，其中的特例是：dp[0]=1和dp[1]=1。嚯！这不就是LeetCode509(斐波那契数列)么。代码实现classSolution:defclimbStairs(self,n:int)->int:ifn复杂度时间复杂度O(n)
Leetcode70题有人问我：烤冷面你这两周怎么总搞简单题？我想说：一步一步来～题干简述给定：假设你正在爬楼梯，需要爬n阶你才能到达楼顶。每次你可以爬1或2个台阶。要求：计算出有多少种爬楼梯的方式。解题思路如果我们缩小视野（把大问题化为小问题），爬到第n阶台阶有两种方式：从n-1阶爬一级台阶从n-2阶爬两级台阶用公式表达：dp[n]=dp[n−1]+dp[n−2]，其中的特例是：dp[0]=1和dp[1]=1。嚯！这不就是LeetCode509(斐波那契数列)么。代码实现classSolution:defclimbStairs(self,n:int)->int:ifn复杂度时间复杂度O(n)
欢迎关注个人公众号：爱喝可可牛奶LeetCode算法训练-动态规划理论知识动态规划当前状态是由前一个状态推导出来的，而贪心没有状态的转移动态规划需要借助dp数组，可能是一维也可能是二维的首先要明确dp数组是用来干什么的，下标对应什么状态如何转移？也就是理清递推公式dp数组如何初始化如何遍历举个栗子模拟推导一遍LeetCode509.斐波那契数分析F(n)=F(n-1)+F(n-2)，其中n>1代码classSolution{publicintfib(intn){if(nLeetCode70.爬楼梯分析错误没有理清递推函数classSolution{publicintclimbStairs(in
欢迎关注个人公众号：爱喝可可牛奶LeetCode算法训练-动态规划理论知识动态规划当前状态是由前一个状态推导出来的，而贪心没有状态的转移动态规划需要借助dp数组，可能是一维也可能是二维的首先要明确dp数组是用来干什么的，下标对应什么状态如何转移？也就是理清递推公式dp数组如何初始化如何遍历举个栗子模拟推导一遍LeetCode509.斐波那契数分析F(n)=F(n-1)+F(n-2)，其中n>1代码classSolution{publicintfib(intn){if(nLeetCode70.爬楼梯分析错误没有理清递推函数classSolution{publicintclimbStairs(in
一、题目大意标签:动态规划https://leetcode.cn/problems/climbing-stairs假设你正在爬楼梯。需要n 阶你才能到达楼顶。每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶呢？示例1：输入：n=2输出：2解释：有两种方法可以爬到楼顶。1阶+1阶2阶示例2：输入：n=3输出：3解释：有三种方法可以爬到楼顶。1阶+1阶+1阶1阶+2阶2阶+1阶提示：1二、解题思路给定n节台阶，每次可以走一步或两步，求一共有多少种方式可以走完这些台阶。这是个斐波那契数列题。定义一个数组dp，dp[i]表示走到第i阶的方法数。因为我们每次可以走一步或两步，所以第i阶可以从第
一、题目大意标签:动态规划https://leetcode.cn/problems/climbing-stairs假设你正在爬楼梯。需要n 阶你才能到达楼顶。每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶呢？示例1：输入：n=2输出：2解释：有两种方法可以爬到楼顶。1阶+1阶2阶示例2：输入：n=3输出：3解释：有三种方法可以爬到楼顶。1阶+1阶+1阶1阶+2阶2阶+1阶提示：1二、解题思路给定n节台阶，每次可以走一步或两步，求一共有多少种方式可以走完这些台阶。这是个斐波那契数列题。定义一个数组dp，dp[i]表示走到第i阶的方法数。因为我们每次可以走一步或两步，所以第i阶可以从第
