> 文档中心 > Python每日一练-----三步问题(爬楼梯进阶版)

Python每日一练-----三步问题(爬楼梯进阶版)

(day13)

目录

🖍题目:

题目分析:

解题思路:

图解分析

🌈动态规划解法

🌈代码注释

🌈优化


🖍题目:

三步问题。有个小孩正在上楼梯,楼梯有n阶台阶,小孩一次可以上1阶、2阶或3阶。实现一种方法,计算小孩有多少种上楼梯的方式。结果可能很大,你需要对结果取模1000000007(%1000000007)。(n范围在[1, 1000000]之间)

🌠示例 1:

输入:1

输出:1

说明:只有1种方法上楼梯

🌠示例 2:

输入:2

输出:2

说明:有2种方法上楼梯

第一种:两次迈1步

第二种:迈2步

🌠示例 3:

输入:3

输出:4

说明:有2种方法上楼梯

第一种:3次都迈1步

第二种:先迈1步再迈2步

第三种:先迈2步再迈1步

第四种:1次迈3步

🌠示例 5:

输入:3

输出:13

说明:有13种方法上楼梯......

题目分析:

上楼梯一次可以迈1步或者是2步或者是3步,那么上n阶楼梯有多少种方法?题目给定了跨步的可选距离,类似于数学中将1,2,3这三个数字排列组合(1,2,3出现的次数<=n)构成<=n个数,这n个数的和为n。如n=3=1+2=1+1+1

解题思路:

这也是动态规划典型题爬楼梯Python每日一练--------递归,动态规划(爬楼梯)_亖夕的博客-CSDN博客_python 递归

的进阶版,不过方法还是差不多的

上动态规划五部曲

1.分析确定dp数组以及其下标的含义

现在确定dp[i]表示从第1阶楼梯爬到第n阶楼梯的所有方法

i  表示第  i  阶楼梯

2.确定递推公式 

顺推

(1)只有第1阶楼梯,n=1

只能用例一上1阶的方法上楼梯

dp[1] = 1

(2)有2阶楼梯,n=2

能使用例一上1阶的方法上第一阶台阶,再例一上1阶的方法上第二阶台阶

或者

使用例二上2阶的方法走直接走上2阶楼梯

dp[2] = dp[1] + dp[1] = dp[2]

(3)有3阶楼梯,n=3

能使用例一上1阶的方法上第一阶台阶,再例一上1阶的方法上第二阶台阶,再例一上1阶的方法上第三阶台阶

或者

使用例二上2阶的方法走走上2阶楼梯,再用例一上1阶的方法上最后一阶台阶

或者

例一上1阶的方法上第一阶台阶,再用例二上2阶的方法走走上最后2阶楼梯

或者

例三的方法直接上三阶楼梯

dp[3] = dp[1] + dp[1] + dp[1] = dp[2] + dp[1]=dp[3]

(3)有n阶台阶, n=n

dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

逆推

当你站再最后一阶楼梯时返回一步,你只可能从第i-1,或i-2阶,或i-3阶楼梯走上来

所以dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

图解分析

 

 

 

3.如何初始化dp数组

从公式dp[i] = dp[i-1] + dp[i-2] + dp[i-3]可知,dp[i]的基础是dp[0],dp[1],和dp[2]

为什么不是dp[1],dp[2],dp[3]?

因为下标i从0开始,所以dp[0],dp[1],dp[2]等同于上面分析的dp[1],dp[2],dp[3]

则dp[0] = 1    dp[1] = 2    dp[2] = 4

4.确定遍历的顺序

由dp[i]的定义,以及公式dp[i]由dp[i-3],dp[i-2],和dp[i-1]推导出来,所以遍历顺序为左到右。

5.举例验证推导的dp数组(公式)是否正确

可以举简单例子如例三

代码实现

🌈动态规划解法

def waysToStep(n):    if n == 1: return 1    elif n == 2: return 2    elif n == 3: return 4    dp = [0] * n    dp[0] = 1    dp[1] = 2    dp[2] = 4    for i in range(3, n): dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] dp[i] %= 1000000007    return dp[-1]

🌈代码注释

def waysToStep(n):    # 可直接返回递归公式的基础    if n == 1: return 1    elif n == 2: return 2    elif n == 3: return 4    # 初始化dp数组    dp = [0] * n    dp[0] = 1    dp[1] = 2    dp[2] = 4    for i in range(3, n):   # 当由公式dp[i-3]为了防止超出列表i从3开始 dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] dp[i] %= 1000000007   # 题目要求的取模操作    return dp[-1]

🌈优化

简单递归后发现目标值仅有dp数组最新三个值确定
所以不必使用数组存储,直接使用滚动数组记录即可

def waysToStep(n):    if n <= 2: return n    a, b, c = 1, 2, 4    for i in range(3, n): a, b, c = b, c, (c + b + a) c %= 1000000007    return c

今天就到这,明天见。🚀

❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄end❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄❄