• 118489

    文章

  • 803

    评论

  • 12

    友链

  • 最近新加了换肤功能,大家多来逛逛吧~~~~
  • 喜欢这个网站的朋友可以加一下QQ群,我们一起交流技术。

动态规划:LC70.爬楼梯

撸了今年阿里、腾讯和美团的面试,我有一个重要发现.......>>

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

思路:
还是三部曲:
1.定义数组:dp[i]--爬第i阶楼梯的方法数
2.数组之间的关系:dp[i]=dp[i-1]+dp[i-2]
3.初始值:dp[0]=1;dp[1]=1---爬第0阶台阶的方法为1,就是不爬

代码:

class Solution {
    public int climbStairs(int n) {
        int[] dp=new int[n+1];
        dp[0]=1;
        dp[1]=1;
        for(int i=2;i<=n;i++){  //先前i<n就不行 ?
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
}

695856371Web网页设计师②群 | 喜欢本站的朋友可以收藏本站,或者加入我们大家一起来交流技术!

0条评论

Loading...


自定义皮肤 主体内容背景
打开支付宝扫码付款购买视频教程
遇到问题联系客服QQ:419400980
注册梁钟霖个人博客