[leetcode]Climbing Stairs @ Python

原題住所: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?
問題解決の考え方:
階段を登る問題.古典的な動的計画問題.毎回1つの階段あるいは2つの階段を上がって、全部で何種類の方法が屋上に着きますかを聞きます.これは実際にフィボナッチ数列の解である.問題を逆方向に解析することができ,n個のステップがあれば,n個のステップを完走する方法はf(n)種である.n個の階段を歩き終えるには2つの方法があり、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]