算法leetcode｜70. 爬楼梯（rust重拳出击）

文章目录

70. 爬楼梯：

假设你正在爬楼梯。需要

n

阶你才能到达楼顶。

每次你可以爬

1

或

2

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

样例 1：

输入：
    
    n = 2
    
输出：
    
    2
    
解释：

    有两种方法可以爬到楼顶。
    1. 1 阶 + 1 阶
    2. 2 阶

样例 2：

输入：
    
    n = 3
    
输出：
    
    3
    
解释：

    有三种方法可以爬到楼顶。
    1. 1 阶 + 1 阶 + 1 阶
    2. 1 阶 + 2 阶
    3. 2 阶 + 1 阶

提示：

• 1 <= n <= 45

分析：

• 面对这道算法题目，二当家的再次陷入了沉思。
• 可以爬一阶或者两阶台阶，那也就是说，除了初始位置，和第一阶台阶，到达其他阶台阶 n 的方式，就只能从 n - 1 阶台阶，或者 n - 2 阶台阶来。
• 这是典型的动态规划，到初始位置和第一阶台阶的方式只有一种，之后到达每一阶台阶的发方法总数都可以动态计算得来，即 **f(x) = f(x − 1) + f(x − 2)**。
• 动态规划方法我觉得很好了，但是由于有规律，用数学的方式计算，当然更快了，另外将前几项列出来，再结合定义，就会发现，到达每一阶台阶的方法总数恰好就是 斐波那契数列。
• 动态规划只能从 1 到 n 按顺序推算，在 n 较大时，效率仍不令人满意，矩阵快速幂，可以有像二分查找一样的效率，数学的知识都还给老师了，有兴趣的可以去研究一下，能看明白，但是过段时间又会忘记，无奈啊，矩阵快速幂 是 矩阵乘法 和 快速幂 的结合，可以先分别了解，再结合理解。
• 所以建议一定要把动态规划优先掌握，其次是快速幂，至于通项公式，数学的方法，很难举一反三，要具体问题具体分析，说到底还是需要掌握数学知识本身，与君共勉。
• 最后，爬楼梯当然要5阶5阶的上才霸气。

题解：

rust：

implSolution{pubfnclimb_stairs(n:i32)->i32{let sqrt5 =5f64.sqrt();let fibn =((1f64+ sqrt5)/2f64).powi(n +1)-((1f64- sqrt5)/2f64).powi(n +1);return(fibn / sqrt5).round()asi32;}}

go：

funcclimbStairs(n int)int{
    sqrt5 := math.Sqrt(5)
    pow1 := math.Pow((1+sqrt5)/2,float64(n+1))
    pow2 := math.Pow((1-sqrt5)/2,float64(n+1))returnint(math.Round((pow1 - pow2)/ sqrt5))}

c++：

classSolution{public:intclimbStairs(int n){constdouble sqrt5 =sqrt(5);constdouble fibn =pow((1+ sqrt5)/2, n +1)-pow((1- sqrt5)/2, n +1);return(int)round(fibn / sqrt5);}};

python：

classSolution:defclimbStairs(self, n:int)->int:
        sqrt5 = math.sqrt(5)
        fibn =pow((1+ sqrt5)/2, n +1)-pow((1- sqrt5)/2, n +1)returnround(fibn / sqrt5)

java：

classSolution{publicintclimbStairs(int n){finaldouble sqrt5 =Math.sqrt(5);finaldouble fibn =Math.pow((1+ sqrt5)/2, n +1)-Math.pow((1- sqrt5)/2, n +1);return(int)Math.round(fibn / sqrt5);}}

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】三连走一波~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://le-yi.blog.csdn.net/ 博客原创~