【Leetcode】70. Climbing Stairs（动态规划）

野性酷女 2022-04-23 15:18 159阅读 0赞

You are climbing a stair case. It takes *n* steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

**Note:** Given *n* will be a positive integer.

**Example 1:**

Input: 2
    Output: 2
    Explanation: There are two ways to climb to the top.
    1. 1 step + 1 step
    2. 2 steps

**Example 2:**

Input: 3
    Output: 3
    Explanation: There are three ways to climb to the top.
    1. 1 step + 1 step + 1 step
    2. 1 step + 2 steps
    3. 2 steps + 1 step

题目大意：

给出n个阶梯，每次只能上1或者2级台阶，输出存在多少组组合。

解题思路：

应该说是规律题，模拟一下前5个答案，就不难发现n的答案是n-1和n-2答案的和。

从题目的角度看，可以这样解释我们知道走到第n级台阶，只有两种方法从n-1级台阶走一步，或者从n-2级台阶走两步。所以其存在的组合即为n-1和n-2答案的和。

class Solution {
    
    public:
        int climbStairs(int n) {
            if(n==0||n==1||n==2){
            	return n;
    		}
    		int l = 1;
    		int r = 2;
    		int ans;
    		for(int i=3;i<=n;i++){
    			ans=r+l;
    			l = r;
    			r = ans;
    		}
    		return ans;
        }
    };

发表评论取消回复

表情：

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

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

相关阅读

相关 LeetCode - Easy - 70. Climbing Stairs

Topic Dynamic Programming Description [https://leetcode.com/problems/climbing-sta

深藏阁楼爱情的钟/ 2022年12月28日 00:40/ 0 赞/ 131 阅读

相关 LeetCode70——Climbing Stairs

LeetCode70——Climbing Stairs 题意：爬楼梯你可以爬一步或者两步，求你到终点时有多少种可能。首先假设终点是3 则你可以： 1.先

喜欢ヅ旅行/ 2022年08月09日 17:47/ 0 赞/ 143 阅读

相关【LeetCode】70. Climbing Stairs

70. Climbing Stairs You are climbing a stair case. It takes n steps to reach to the

柔光的暖阳◎/ 2022年07月26日 08:35/ 0 赞/ 158 阅读

相关 [leetcode]: 70. Climbing Stairs

1.题目 You are climbing a stair case. It takes n steps to reach to the top. Each time

拼搏现实的明天。/ 2022年06月15日 02:11/ 0 赞/ 140 阅读

相关 leetcode 70. Climbing Stairs DP动态规划 + 斐波那契序列

You are climbing a stair case. It takes n steps to reach to the top. Each time you can

落日映苍穹つ/ 2022年06月09日 11:56/ 0 赞/ 141 阅读

相关【LeetCode】70. Climbing Stairs

> You are climbing a stair case. It takes n steps to reach to the top. > > Each time yo

阳光穿透心脏的1/2处/ 2022年05月21日 07:20/ 0 赞/ 133 阅读

相关 70. Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top. Each time you can

浅浅的花香味﹌/ 2022年05月16日 15:56/ 0 赞/ 126 阅读

相关【Leetcode】70. Climbing Stairs（动态规划）

You are climbing a stair case. It takes n steps to reach to the top. Each time you can

野性酷女/ 2022年04月23日 15:18/ 0 赞/ 160 阅读

相关【LeetCode】70. Climbing Stairs

Introduction You are climbing a stair case. It takes n steps to reach to the top. E

深藏阁楼爱情的钟/ 2022年03月15日 09:16/ 0 赞/ 161 阅读

相关（Java）leetcode-70 Climbing Stairs（递归，备忘录，动态规划）

爬楼梯 You are climbing a stair case. It takes n steps to reach to the top. Each time you

忘是亡心i/ 2022年03月07日 02:04/ 0 赞/ 185 阅读