9

算法简单题，吾辈重拳出击 - 动态规划之爬楼梯

 2 years ago
source link: https://blog.51cto.com/u_13961087/5592432
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

算法简单题，吾辈重拳出击 - 动态规划之爬楼梯

推荐 原创

DP 动态规划接着冲！经典之爬楼梯题目~

算法简单题，吾辈重拳出击 - 动态规划之爬楼梯_i++

题：

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

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

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



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



  • ​​1 <= n <= 45​​



解：



看完题目，但又一点思路没有，可以尝试枚举。很多算法题都是这样，没有思路，就枚举几个，思路就会来了。



在示例的基础上，再加几个示例，加到有思路为止🐶：



1. 1+1
2. 2



1. 1+1+1
2. 1+2
3. 2+1



1.  1+1+1+1
2.  1+1+2
3.  1+2+1
4.  2+1+1
5.  2+2



1. 1+1+1+1+1
2. 1+1+1+2
3. 1+1+2+1
4. 1+2+1+1
5. 2+1+1+1
6. 2+1+2
7. 1+2+2
8. 2+2+1



1. 1+1+1+1+1+1
2. 1+1+1+1+2
3. 1+1+1+2+1
4. 1+1+2+1+1
5. 1+2+1+1+1
6. 2+1+1+1+1
7. 1+1+2+2
8. 1+2+1+2
9. 1+2+2+1
10. 2+1+2+1
11. 2+1+1+2
12. 2+2+1+1
13. 2+2+2



......



方法数依次为：1、2、3、5、8、13......



就纯数学角度来看，观察这个数列，找规律，这不就是斐波那契数列吗？



每一项等于前两项的和：



f(x)=f(x-1)+f(x-2)



/**
 * @param {number} n
 * @return {number}
 */
var climbStairs = function(n) {
    let a = 1
    if(n===1) return 1
    let b = 2
    if(n===2) return 2
    let res = 0
    for(let i=0;i<n-2;i++){
         res = a+b
         a = b
         b = res
    } 
    return res
}



算法简单题，吾辈重拳出击 - 动态规划之爬楼梯_i++_02



用 动态规划 的思维来解释上述斐波那契数列，就不用枚举找规律了：



将本题问题分成多个子问题：



爬第n阶楼梯的方法数量 = （爬上 n−1 阶楼梯的方法数量）+（爬上 n−2 阶楼梯的方法数量）



用表达式表达即：​​dp[n]=dp[n−1]+dp[n−2]​​



var climbStairs = function(n) {
    const dp = [];
    dp[0] = 1;
    dp[1] = 1;
    for(let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
};






小结：



动态规划的很多题，思维都是考虑最后一项和前面一项或多项的关系，将一个大问题抽象为一个小的具体的表达式。



OK，以上便是本篇分享。点赞关注评论，为好文助力👍
我是掘金安东尼 🤠 100 万人气前端技术博主 💥 INFP 写作人格坚持 1000 日更文 ✍ 关注我，安东尼陪你一起度过漫长编程岁月 🌏

        

        

            

                report
            

        

    







        
Recommend

        



                

    
About Joyk

    
 





Aggregate valuable and interesting links.

Joyk means Joy of geeK