- /*
- * @lc App=leetcode.cn id=70 lang=c
- *
- * [70] 爬楼梯
- *
- * https://leetcode-cn.com/problems/climbing-stairs/description/
- *
- * algorithms
- * Easy (44.44%)
- * Total Accepted: 33.5K
- * Total Submissions: 75.4K
- * Testcase Example: '2'
- *
- * 假设你正在爬楼梯. 需要 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 阶
- *
- *
- */
- int climbStairs(int n) {
- int f1 = 1;
- int f2 = 2;
- int f3;
- int i =2;
- if(n==1){
- return 1;
- }
- if(n<1){
- return 0;
- }
- while(i<n){
- f3 = f1+f2;
- f1 = f2;
- f2 = f3;
- i++;
- }
- return f3;
- }
n=1 的时候值为 1,n=2 的时候值为 2.n 等于 3 的时候值为 3,f3=f1+f2 是典型的斐波那契数列
所以求 n 阶需要多少步, 其实就是求 f(n) 的过程.
------------------------------------------------------------------------------------------------------------------------
python:
- #
- # @lc App=leetcode.cn id=70 lang=python3
- #
- # [70] 爬楼梯
- #
- # https://leetcode-cn.com/problems/climbing-stairs/description/
- #
- # algorithms
- # Easy (44.44%)
- # Total Accepted: 33.5K
- # Total Submissions: 75.4K
- # Testcase Example: '2'
- #
- # 假设你正在爬楼梯. 需要 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 阶
- #
- #
- #
- class Solution:
- def climbStairs(self, n: int) -> int:
- f1=1
- f2=2
- f3=0
- i=2
- if n==1:
- return 1
- if n==2:
- return 2
- if n<1:
- return 0
- while i<n:
- f3 = f1+f2
- f1 = f2
- f2 = f3
- i+=1
- return f3
来源: http://www.bubuko.com/infodetail-2984873.html