Leetcode70爬楼梯---两种解法

水深无声 2022-10-27 12:07 143阅读 0赞

# Leetcode70爬楼梯—两种解法 #

[题目链接][Link 1]

## 题目 ##

### 题目描述 ###

> 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。  
> 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？  
> **注意：给定 n 是一个正整数。**

### 示例 ###

#### 示例1 ####

输入： 2
    输出： 2
    解释： 有两种方法可以爬到楼顶。
    1.  1 阶 + 1 阶
    2.  2 阶

#### 示例2 ####

输入： 3
    输出： 3
    解释： 有三种方法可以爬到楼顶。
    1.  1 阶 + 1 阶 + 1 阶
    2.  1 阶 + 2 阶
    3.  2 阶 + 1 阶

## 解题思路 ##

### 思路一、简单动态规划 ###

> 推导公式：dp\[i\]==dp\[i-1\]+dp\[i-2\]

代码描述:

class Solution {
        
        public int climbStairs(int n) {
        
        	int pre1=1;
        	int pre2=1;
        	for(int i=2;i<=n;i++) {
        
        		int tem=pre1+pre2;
        		pre1=pre2;
        		pre2=tem;
        	}
        	return pre2;
        }
    }

### 思路二、转化为完全背包问题 ###

说明:当问题扩展到你可以爬1、2、3 …m阶楼梯时候有多少种爬法，其实本质上推导公式与思路一没有本质不同，但这其实是完全背包的一种思想，有必要将该问题从问题本身抽象出来，值得本人学习。  
代码描述:

class Solution {
        
        public int climbStairs(int n) {
        
            //转化为完全背包问题求解
            int m=2;
            int[] dp=new int[n+1];
            dp[0]=1;
            for(int i=1;i<=n;i++){
        
                for(int j=1;j<=m;j++){
        
                    if(j<=i) dp[i]+=dp[i-j];
                    else break;
                }
            }
            return dp[n];
        }
    }

[Link 1]: https://leetcode-cn.com/problems/climbing-stairs/

发表评论取消回复

表情：

评论列表（有 0 条评论，143人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode70--爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。示例 1：输入

心已赠人/ 2022年11月17日 05:24/ 0 赞/ 163 阅读

相关 Leetcode70爬楼梯---两种解法

Leetcode70爬楼梯—两种解法 [题目链接][Link 1] 题目题目描述 > 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 > 每次你可以爬

水深无声/ 2022年10月27日 12:07/ 0 赞/ 144 阅读

相关 Leetcode70. 爬楼梯

难度：`简单` 题目描述： > 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 > > 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？ > >

痛定思痛。/ 2022年09月08日 14:00/ 0 赞/ 157 阅读

相关 Leetcode 70. 爬楼梯

题目重述假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。

电玩女神/ 2022年09月08日 05:54/ 0 赞/ 135 阅读

相关 LeetCode70.爬楼梯

假设你正在爬楼梯。需要 n 步你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。示例 1

雨点打透心脏的1/2处/ 2022年05月26日 06:46/ 0 赞/ 163 阅读

相关 70. 爬楼梯 python3 四种解法

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。示例 1：输入

阳光穿透心脏的1/2处/ 2022年05月08日 14:38/ 0 赞/ 135 阅读

相关 70. 爬楼梯 python3 四种解法

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。示例 1：输入

布满荆棘的人生/ 2022年05月07日 08:16/ 0 赞/ 131 阅读

相关 leetcode 70. 爬楼梯

【前言】 python刷leetcode题解答目录索引：[https://blog.csdn.net/weixin\_40449300/article/

短命女/ 2022年04月16日 02:49/ 0 赞/ 179 阅读

相关 leetcode:70. 爬楼梯

题目: 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。示例

分手后的思念是犯贱/ 2022年04月10日 03:57/ 0 赞/ 181 阅读

相关 leetcode 70 爬楼梯

用阶乘公式算数字越界了，的确进行了一些不必要的计算，代码贴着留个纪念,局限:能进行小数字的计算 C++: 1 class Solution {

客官°小女子只卖身不卖艺/ 2021年12月21日 01:19/ 0 赞/ 235 阅读