70-爬楼梯

CompileYouth 发布于2019-08-19 11:05 / 667人阅读

摘要：前言最近在练习动态规划的题目，然后就随便选择了一道简单的题目爬楼梯，题目如下假设你正在爬楼梯。斐波那契数列爬楼梯实现代码爬楼梯

前言

最近在练习动态规划的题目，然后就随便选择了一道简单的题目——爬楼梯，题目如下：

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

示例 1：

输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

示例 2：

输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

解题思路

这道题目虽然分类是动态规划，但是实际上就是个斐波那契数列，不过是一个当入参为n时，需对应的是斐波那契数列的f(n+1)。
斐波那契数列：

f(0)=0
f(1)=1
f(2)=f(1)+f(0)=1
f(3)=f(2)+f(1)=2
f(4)=f(3)+f(2)=3
f(5)=f(4)+f(3)=5
f(6)=f(5)+f(4)=8
f(7)=f(6)+f(5)=13

爬楼梯:

c(0)=f(0)=0
c(1)=f(0)+f(1)=f(2)=1
c(2)=f(1)+f(2)=f(3)=2
c(3)=f(2)+f(3)=f(4)=3
c(4)=f(3)+f(4)=f(5)=5
c(5)=f(4)+f(5)=f(6)=8
c(6)=f(5)+f(6)=f(7)=13

实现代码

    /**
     * 爬楼梯
     * @param n
     * @return
     */
    public int climbStairs(int n) {
        if(n==1){
            return 1;
        }else if(n==2){
            return 2;
        }else{
            int f1 = 1;
            int f2 = 2;
            int result = 0;
            for (int i = 3; i <=n; ++i){
                result=f1+f2;
                f1 = f2;
                f2 = result;
            }
            return result;
        }
    }

GPU云服务器云服务器爬楼梯楼梯兔子上楼梯c语言 70cdn

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/76982.html

【Leetcode】70. 爬楼梯

摘要：题目假设你正在爬楼梯。需要阶你才能到达楼顶。你有多少种不同的方法可以爬到楼顶呢注意给定是一个正整数。示例输入输出解释有两种方法可以爬到楼顶。阶阶阶阶阶阶阶题解这个题目只要模拟一下基本就能想到是，状态方程写出来就是斐波那契数列。题目假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。示...

raoyi 2019-07-24 10:49 评论0 收藏0
【Leetcode】70. 爬楼梯

摘要：题目假设你正在爬楼梯。需要阶你才能到达楼顶。你有多少种不同的方法可以爬到楼顶呢注意给定是一个正整数。示例输入输出解释有两种方法可以爬到楼顶。阶阶阶阶阶阶阶题解这个题目只要模拟一下基本就能想到是，状态方程写出来就是斐波那契数列。题目假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。示...

187J3X1 2019-06-26 17:49 评论0 收藏0
【Leetcode】70. 爬楼梯

摘要：题目假设你正在爬楼梯。需要阶你才能到达楼顶。你有多少种不同的方法可以爬到楼顶呢注意给定是一个正整数。示例输入输出解释有两种方法可以爬到楼顶。阶阶阶阶阶阶阶题解这个题目只要模拟一下基本就能想到是，状态方程写出来就是斐波那契数列。题目假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定 n 是一个正整数。示...

wow_worktile 2019-07-25 14:26 评论0 收藏0
LeetCode 之 JavaScript 解答第70题 —— 爬楼梯（Climbing Stair

摘要：小鹿题目假设你正在爬楼梯。需要阶你才能到达楼顶。你有多少种不同的方法可以爬到楼顶呢注意给定是一个正整数。算法思路二种解决思路，第一利用递归第二利用动态规划。就是因为有了重复元素的计算，导致了时间复杂度成指数的增长。 Time：2019/4/12Title:Clibing SrairsDifficulty: EasyAuthor:小鹿题目：Climbing Stairs You a...

chemzqm 2019-08-23 16:55 评论0 收藏0