70. Climbing Stairs

浅浅的花香味﹌ 2022-05-16 15:56 131阅读 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层，总有多少种走法。

方法一：动态规划，状态转移方程是 count\[i\] = count\[i-1\] + count\[i-2\];  count\[i\]表示i个台阶有多少种走法。

class Solution {
    public:
        int climbStairs(int n) {
             if(n<=2)
              return n;
    
            vector<int> count(n);
            count[0] =1;
            count[1] =2;
            
            for(int i=2;i<n;i++)
            {
              count[i] = count[i-1] + count[i-2];
            }      
            return  count[n-1];
        }
    };

发表评论取消回复

表情：

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

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

相关阅读

相关 LeetCode - Easy - 70. Climbing Stairs

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

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

相关 LeetCode70——Climbing Stairs

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

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

相关【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 赞/ 165 阅读

相关 70. Climbing Stairs （爬楼梯）

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

缺乏、安全感/ 2022年07月15日 01:17/ 0 赞/ 139 阅读

相关 70. Climbing Stairs （爬楼梯）

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

我就是我/ 2022年07月15日 01:17/ 0 赞/ 149 阅读

相关 [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 赞/ 148 阅读

相关【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 赞/ 143 阅读

相关 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 赞/ 132 阅读

相关【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 赞/ 171 阅读

相关 70-爬楼梯（Climbing Stairs）

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

秒速五厘米/ 2022年01月25日 17:41/ 0 赞/ 248 阅读