当前位置：网站首页>力扣70-爬楼梯——动态规划

力扣70-爬楼梯——动态规划

2022-07-17 17:15:00 【张怼怼√】

题目描述

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

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

解题思路

首先考虑一层台阶：1种方法：1；
两层台阶：2种方法：1+1，2；
三层台阶：3种方法：1+1+1，1+2，2+1；
四层台阶：5种方法：1111，121，211，112，22；
然后发现存在一个规律：当前 i 层台阶的方法 = i - 1 方法 + i - 2 方法；
所以能够写出动态规划状态转移方程dp【i】= dp【i-1】 + dp【i - 2】；
所以建立三个变量 p q r 分别代表 i-2 ，i-1，i 的方法数；
通过遍历就可以求解出台阶数为 n 时的爬楼梯方法。

输入输出示例

代码

class Solution {
    public int climbStairs(int n) {
        if(n <= 2) return n;
        int p = 1;
        int q = 2;
        int r = 0;
        for(int i = 2; i < n; i++){
            r = p + q;
            p = q;
            q = r;
        }
        return r;
    }
}

原网站

版权声明
本文为[张怼怼√]所创，转载请带上原文链接，感谢
https://blog.csdn.net/weixin_44564247/article/details/125797724