算法打卡Week15

2021/7/5 14:20:58

本文主要是介绍算法打卡Week15,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目:爬楼梯
链接:https://leetcode-cn.com/problems/climbing-stairs/

假设你正在爬楼梯。需要 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 阶

思路:
按照题意,我们可以先确认爬楼梯的方法有两种,第一种方法为只爬1阶,第二种方法为一下子爬2阶。
当阶梯为1的时候,爬楼梯的方法只有一种,我们可以记为 f(1)=1;
当阶梯为2的时候,我们可以考虑先爬1阶还是2阶,最后爬楼梯的方法有两种①1阶 + 1阶 ②2阶,我们可以记为f(2)=2;
当阶梯为3的时候,我们也是先考虑先爬1阶还是2阶,如果我们先按第一种方式爬,则剩余2层;按第二种方式爬,则剩余一层,我们可以记作f(3) = f(2) + f(1),而f(1)和f(2)前面已经算出,所以f(3)=3;
参考上面我们可以推出f(n) = f(n-1) + f(n-2) ,n≥3 ,n为阶梯层数

第一种方式,通过递归方式解决,但n过大的时候会超出时间限制

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 1:
        	return 1
        if n == 2:
        	return 2
        return self.climbStairs(n-1) + self.climbStairs(n-2)

第二种方式,非递归

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 1:
        	return 1
        dip = [ 0 for _ in range(n+1)]
        dip[1] = 1
        dip[2] = 2
        for i in range(3, n+1):
        	dip[i] = dip[i-1] + dip[i -2]
        return dip[n]


这篇关于算法打卡Week15的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程