Climbing stairs (70)

本文主要是介绍Climbing stairs (70)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

写了个top-down的divide and conquer程序，可惜超时了。

class Solution:def climbStairs(self, n: int) -> int:# divide and conquer?if n == 0:return 1if n <= 1:return self.climbStairs(n-1)if n >= 2:return self.climbStairs(n-1) + self.climbStairs(n-2)

写个bottom up的DP程序，还是比较清楚的。
induction的初始值，以及推导步骤。
就是到每个节点的可能有两种：1种是经过它前面的一个节点，再一跳。另一种是不经过它前面的节点，从它前两个那里，跳两个台阶。
所以ways[n] = ways[n-1]+ways[n-2]

class Solution:def climbStairs(self, n: int) -> int:# treat it as a DP problem# number of possible ways to the ith stepways = [0 for i in range(n)]if n==1: return 1if n==2: return 2ways[0] = 1   # only one choice for 1 stepways[1] = 2   # only two choices for two stepsfor i in range(2,n):ways[i] = ways[i-1] + ways[i-2] # only 2 choices, passing i-1th node or not passing it# passing the i-1th node by doing one step# not passing the i-1th node by doing two steps# so when combined, it will all the possibilities.return ways[n-1]

因为其实用不到存储那么多值，只需要两个变量就可以了。
主要是需要搞好ways_prev2, 和ways_prev初始值的顺序，不然就错了。
这就是个斐波那契数列。

class Solution:def climbStairs(self, n: int) -> int:# treat it as a DP problem# number of possible ways to the ith stepif n==1: return 1if n==2: return 2ways_prev2 = 1   # only one choice for 1 stepways_prev = 2   # only two choices for two stepsfor i in range(2,n):ways = ways_prev + ways_prev2 # only 2 choices, passing i-1th node or not passing it# passing the i-1th node by doing one step# not passing the i-1th node by doing two steps# so when combined, it will all the possibilities.ways_prev2 = ways_prevways_prev = waysreturn ways

这篇关于Climbing stairs (70)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---