第107回【Python】階段の上り方 1、階段の上り方 2

現在取り組んでいるのは、paiza ラーニング問題集「DP メニュー」になります。

はじめに

猫とキャンプと野球観戦と AWS が大好きな旦那、LeoSaki です。モフモフしたい。

Python をゼロから勉強してみよう、のコーナー 107 回目です。

iPhone の電池交換をしました。Apple Care+ のルール、蓄電容量が本来の 80 % 未満に低下している場合は無償ってなかなか酷いと思います。85 % くらいで目に見えて充電が切れるのが早くなるのに。我慢して我慢してとうとう 79 % になったので、無償交換してもらえました。予約して行ったのに 1 時間以上待たされたけど。

それでは、今日も頑張ってみようと思います。

階段の上り方 1

整数 n が与えられます。
階段を上るのに、1 歩で 1 段または 2 段を上ることができるとき、n 段の階段を上る方法は何通りあるでしょうか。

(ヒント)

これまでは問題文中に具体的な漸化式が書かれていましたが、この問題にはありません。自分で漸化式を立てる必要があります。

部分問題として、1 ~ n-1 段の階段を上る方法が何通りあるか、という問題を考えてみましょう。この部分問題の答えが求まっているとして、n 段の階段を上る方法が何通りあるかを考えてみましょう。n 段目に到達するには、n-1 段目から1段上る方法と、n-2 段目から2段上る方法の2種類が考えられます。dp[n] を n 段の階段を上る方法の数とすれば、この関係は dp[n] = dp[n-1] + dp[n-2] で表すことが出来ます。よって、0段の階段を上る方法が1通り (何もしない) であることを踏まえると、以下のようにして答えを求めることが出来ます。

dp[0] <- 1

for i = 1 to n
    dp[i] <- 0
    if i >= 1 then
        dp[i] <- dp[i] + dp[i-1]    // i-1 段目から1段上って i 段へ到達
    if i >= 2 then
        dp[i] <- dp[i] + dp[i-2]    // i-2 段目から2段上って i 段へ到達

print dp[n]
n

すべてのテストケースにおいて、以下の条件をみたします。

・ 1 ≦ n ≦ 40

入力例

3

出力例

3

この問題、DP 問題の基本中の基本の考え方が学べる気がします。

Python
n = int(input())
dp = [1] * (n+1)
for i in range(1,n+1):
    dp[i] = 0
    if i >= 1:
        dp[i] = dp[i] + dp[i-1]
    if i >= 2:
        dp[i] = dp[i] + dp[i-2]
print(dp[n])
VBA
N = Cells(1, 1)
Dim dp() As Long
ReDim dp(N)
dp(0) = 1
For i = 1 To N
    dp(i) = 0
    If i >= 1 Then
        dp(i) = dp(i) + dp(i - 1)
    End If
    If i >= 2 Then
        dp(i) = dp(i) + dp(i - 2)
    End If
Next
Debug.Print dp(N)

階段の上り方 2

整数 n, a, b が与えられます。
階段を上るのに、1歩で a 段または b 段を上ることができるとき、n 段の階段を上る方法は何通りあるでしょうか。

(ヒント)

前問とやることは同じです。ただ、n, a, b の値によっては答えが0になることがあるので注意しましょう。例えば、n = 4, a = 3, b = 5 のとき、答えは0です。(1歩で3段か5段上ることができるとき、ちょうど4段の階段を上る方法は存在しない)

n a b

すべてのテストケースにおいて、以下の条件をみたします。

・ 1 ≦ n ≦ 40
・ 1 ≦ a ≦ 5
・ 1 ≦ b ≦ 5
・ a ≠ b

入力例

11 3 4

出力例

3

この問題は、前問の応用。ただ、0 という解答が発生する可能性があることに注意。

Python
n,a,b = map(int,input().split())
dp = [0] * (n+1)
dp[0] = 1
for i in range(1,n+1):
    if i >= a:
        dp[i] = dp[i] + dp[i-a]
    if i >= b:
        dp[i] = dp[i] + dp[i-b]
print(dp[n])
VBA
NAB = Split(Cells(1, 1), " ")
N = Val(NAB(0))
A = Val(NAB(1))
b = Val(NAB(2))
Dim dp() As Long
ReDim dp(N)
dp(0) = 1
For i = 1 To N
    If i >= A Then
        dp(i) = dp(i) + dp(i - A)
    End If
    If i >= b Then
        dp(i) = dp(i) + dp(i - b)
    End If
Next
Debug.Print dp(N)

最後に

頭の中で、その配列に今現在何が入っているかを思い浮かべて、理解して組み立てていかないと、こんがらがってしまいそう。結局、メモを手元に置いて手書きで確認しながら問題を解くようにしています。アナログ。

この手法は結構、いろいろなところで使えると思うので、再度見直しながら、頭に叩き込もうと思いました。

引き続き、よろしくお願いいたします！

Python学習,Python,paiza

Posted by LeoSaki