【LeetCode】70. Climbing Stairsを解く

問題へのリンク

問題概要

階段を上ることを考える．頂上に到達するにはnステップかかる．
一度に階段を1もしくは2ステップ上ることができるとき，頂上への上り方は何通りあるか答える．

例：

Input: n = 2
Output: 2

1. 1 step + 1 step
2. 2 step

制約

$1 \leq n \leq 45$

考えたこと

$n = 1$：1通り

1. 1 step

$n = 2$：2通り

1. 1 step + 1 step
2. 2 step

$n = 3$：3通り
階段を■で表すと，下図のようにn=1の状況から2 step進む方法と，n=2の状態から1 step進む方法がある

2 step
┌───┐
■ ■ ■
　└─┘
  1 step

従って，

n=1 + 2 step
1. 1 step + 2 step

n=2 + 1 step
2. 1 step + 1 step + 1 step
3. 2 step + 1 step

の3通りとなる．

このように，n-2とn-1の答えが分かればnの答えが導けるような問題であることが分かる．

従って，DPを用いて解くことができる．

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        dp = [0]*(n+1)
        dp[0] = 1
        dp[1] = 1
        for i in range(2,n+1):
            dp[i] = dp[i-2] + dp[i-1]
        return dp[n]

Tips

配列dp[i]は$n=i$に相当している．

問題では，$n=0$は範囲外であるが，便宜上$n=0$の時は何もしないという1通りあるものと想定している．