开发者社区云计算文章正文

爬楼梯（动态规划）

2023-02-22 78 发布于吉林

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

输入：n = 2

输出：2

解释：有两种方法可以爬到楼顶。

1 阶 + 1 阶
2 阶
示例 2：

输入：n = 3

输出：3

解释：有三种方法可以爬到楼顶。

1 阶 + 1 阶 + 1 阶
1 阶 + 2 阶

2 阶 + 1 阶

提示：

1 <= n <= 45

来源：力扣（LeetCode）

先用数学归纳法推断出规律。

class Solution {
    public int climbStairs(int n) {
        //for(){}
        if(n==1){
            return 1;
        }else{
            int sum=0;
            int a=1;
            int b=1;
            for(int i=1;i<n;i++){
                sum=a+b;
                a=b;
                b=sum;
            }
            return sum;
        }
    }
}