网站建设 网址导航,优化排名推广教程网站,wordpress地图页面如何添加,平面设计哪个网站素材好【玩转动态规划专题】70. 爬楼梯【简单】
1、力扣链接
https://leetcode.cn/problems/climbing-stairs/description/
2、题目描述
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢#xff1f;
示例 1
示例 1
输入n 2 输出2 解释有两种方法可以爬到楼顶。
1 阶 1 阶2 阶 示例 2
输入n 3 输出3 解释有三种方法可以爬到楼顶。
1 阶 1 阶 1 阶1 阶 2 阶2 阶 1 阶
提示
1 n 45
3、题目分析
动态规划五部曲 1、确定dp数组dp table以及下标的含义 dp[i]以及下标的含义i阶楼梯有dp[i]种方式到达楼顶 2、确定递推公式 dp[i] dp[i-1]dp[i-2]; 3、dp数组如何初始化 注意读题dp[0]是不存在的 题目中 1 n 45 所以初始化时从1开始虽然设定dp[0] 1也可以通过但dp[0] 1的意义不正确与dp[i]数组的含义违背【0阶楼梯有1种方式到达楼顶明显不对】 正确初始化 dp[1] 1, dp[2]2 4、确定遍历顺序 从前往后直接遍历 5、举例推导dp数组
4、代码实现
1、Java
class Solution {public int climbStairs(int n) {//dp[i]以及下标的含义i阶楼梯有dp[i]种方式到达楼顶int[] dp new int[n1];dp[1] 1;dp[2] 2;if(n 3){return dp[n];}for(int i3;in;i){dp[i] dp[i-1] dp[i-2];}return dp[n];}
}2、C
class Solution {
public:int climbStairs(int n) {if (n 1) return n; // 因为下面直接对dp[2]操作了防止空指针vectorint dp(n 1);dp[1] 1;dp[2] 2;for (int i 3; i n; i) { // 注意i是从3开始的dp[i] dp[i - 1] dp[i - 2];}return dp[n];}
};3、python
class Solution:def climbStairs(self, n: int) - int:if n 1:return ndp [0] * (n 1)dp[1] 1dp[2] 2for i in range(3, n 1):dp[i] dp[i - 1] dp[i - 2]return dp[n]4、go
func climbStairs(n int) int {if n 1 {return 1}dp : make([]int, n1)dp[1] 1dp[2] 2for i : 3; i n; i {dp[i] dp[i-1] dp[i-2]}return dp[n]
}
