动态规划之Climbing Stairs(爬楼梯) java实现

小鱼儿 2022-12-30 08:00 154阅读 0赞

### 问题 ###

有一个楼梯，总共有n阶台阶。每一次，可以上一个台阶，也可以上两个台阶。问，爬这样的一个楼梯，一共有多少不同的方法？  
如n=3，可以爬上这个梯子的方法有：\[1,1,1\],\[1,2\],\[2,1\]，所以答案为3。

### 问题分析 ###

动态规划的问题，我们先把问题转化为递归问题进行分析：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21hbWVuZzE5ODg_size_16_color_FFFFFF_t_70]  
看到上面的图，大家是不是有一种熟悉的感觉，没错，这就是斐波那契数列的递归图。先通过递归方式解决问题，然后以动态规划方式解决问题。

### 问题解决 ###

##### 递归方式 #####

public static int computeWay(int n) { 
        if (n == 0 || n == 1)
            return 1;
        return computeWay(n-1) + computeWay(n-2);
    }

##### 动态规划方式 #####

public static int computeWayBetter(int n) { 
            int[] res = { 0,1};
            if (n < 2) { 
                return res[n];
            }
            int first = 1;
            int second = 1;
            int result = 0;
            for (int i=2;i<=n;i++) { 
                result = first+second;
                first = second;
                second = result;
            }
            return result;
        }

注意：n从0开始

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L21hbWVuZzE5ODg_size_16_color_FFFFFF_t_70]: /images/20221120/0c158fa6eebe4fcb87936472f9412fc1.png

发表评论取消回复

表情：

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

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

相关阅读

相关动态规划之爬楼梯

[70. 爬楼梯][70.] 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

迷南。/ 2023年09月30日 21:14/ 0 赞/ 29 阅读

相关动态规划之Climbing Stairs(爬楼梯) java实现

问题有一个楼梯，总共有n阶台阶。每一次，可以上一个台阶，也可以上两个台阶。问，爬这样的一个楼梯，一共有多少不同的方法？如n=3，可以爬上这个梯子的方法有：\[1,

小鱼儿/ 2022年12月30日 08:00/ 0 赞/ 155 阅读

相关 LeetCode-Climbing Stairs（爬楼梯问题）

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

左手的ㄟ右手/ 2022年08月06日 15:24/ 0 赞/ 151 阅读

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

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

相关 [Leetcode][python]Climbing Stairs/爬楼梯

题目大意一共有n级楼梯，每次能够爬一级或两级，共有多少种不同的爬法爬到顶端。注意：第一级楼梯也要上，也就是说第二个楼梯就有两种走法。解题思路动态规划，状态转

短命女/ 2022年06月07日 08:11/ 0 赞/ 169 阅读

相关 LeetCode 70.Climbing Stairs (爬楼梯)

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

迷南。/ 2022年05月10日 05:50/ 0 赞/ 183 阅读

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

相关 LeetCode:70. Climbing Stairs(爬楼梯问题)

> 文章最前：我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。这博客是记录我学习的点点滴滴，如果您对 Python、Java、AI、算法

约定不等于承诺〃/ 2022年04月11日 10:16/ 0 赞/ 162 阅读

相关 70-爬楼梯（Climbing Stairs）

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

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