Python学习教程:算法如何解决楼梯台阶问题

No Comments

Python学习教程:算法如何解决楼梯台阶问题
这期的Python学习教程跟咱们讲一下算法问题,以楼梯台阶为例!有一个有N个台阶的楼梯,你一次能够爬1或2个台阶。给定N,编写一个函数,回来爬完楼梯的办法数量。过程的次序很重要。例如,假如N是4,那么有5种办法:1,1,1,12,1,11,2,11,1,22,2假如规则的不是一次只能爬1或2步,而是能够运用正整数X调集内的恣意数字爬楼梯,那会怎么样?例如,假如X = {1,3,5},则表明一次爬高1,3或5阶楼梯。解决方案从一些测验事例开端总是好的做法。让咱们从小的事例开端,看看能否找到某种规则。N = 1,1种爬楼办法:[1]N = 2,2种爬楼办法:[1,1],[2]N = 3,3种爬楼办法:[1,2],[1,1,1],[2,1]N = 4,5种爬楼办法:[1,1,2],[2,2],[1,2,1],[1,1,1,1],[2,1,1]你有没有注意到什么?请看N = 3时,爬完3阶楼梯的办法数量是3,根据N = 1和N = 2。存在什么联系?爬完N = 3的两种办法是首要抵达N = 1,然后再往上爬2步,或抵达N = 2再向上爬1步。所以 f(3) = f(2) + f(1)。这对N = 4是否建立呢?是的,这也是建立的。由于咱们只能在抵达第三个台阶然后再爬一步,或许在到了第二个台阶之后再爬两步这两种办法爬完4个台阶。所以f(4) = f(3) + f(2)。所以联系如下: f(n) = f(n – 1) + f(n – 2),且f(1) = 1和f(2) = 2。这便是斐波那契数列。def fibonacci(n):if n <= 1:return 1return fibonacci(n – 1) + fibonacci(n – 2)当然,这很慢(O(2^N))——咱们要做许多重复的核算!经过迭代核算,咱们能够更快:def fibonacci(n):a, b = 1, 2for _ in range(n – 1):a, b = b, a + breturn a现在,让咱们测验归纳咱们学到的东西,看看是否能够应用到从调集X中取步数这个要求下的爬楼梯。相似的推理告知咱们,假如X = {1,3,5},那么咱们的算法应该是f(n) = f(n – 1) + f(n – 3) + f(n – 5)。假如n <0,那么咱们应该回来0,由于咱们不能爬负数。def staircase(n, X):if n < 0:return 0elif n == 0:return 1elif n in X:return 1 + sum(staircase(n – x, X) for x in X if x < n)else:return sum(staircase(n – x, X) for x in X if x < n)这也很慢(O(|X|^N)),由于也重复核算了。咱们能够运用动态编程来加快速度。每次的输入cache[i]将包括咱们能够用调集X抵达台阶i的办法的数量。然后,咱们将运用与之前相同的递归从零开端构建数组:def staircase(n, X):cache = [0 for _ in range(n + 1)]cache[0] = 1for i in range(n + 1):cache[i] += sum(cache[i – x] for x in X if i – x > 0)cache[i] += 1 if i in X else 0return cache[-1]现在时刻复杂度为O(N * |X|),空间复杂度为O(N)。

发表评论

电子邮件地址不会被公开。 必填项已用*标注