[leetcode]Climbing Stairs @ Python
浏览数：55 /
时间：2015年06月08日
原题地址：https://oj.leetcode.com/problems/climbing-stairs/
题意：
You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
解题思路：
爬楼梯问题。经典的动态规划问题。每次上一个台阶或者两个台阶，问一共有多少种方法到楼顶。这个实际上就是斐波那契数列的求解。可以逆向来分析问题，如果有n个台阶，那么走完n个台阶的方式有f(n)种。而走完n个台阶有两种方法，先走完n-2个台阶，然后跨2个台阶；先走完n-1个台阶，然后跨1个台阶。所以f(n) = f(n-1) + f(n-2)。
代码：
class Solution: # @param n, an integer # @return an integer def climbStairs(self, n): dp = [1 for i in range(n+1)] for i in range(2, n+1): dp[i] = dp[i-1] + dp[i-2] return dp[n]
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
