#19/20 Recursion: Davis' Staircase [Cracking the Coding Interview Challenges]

code interview hackerrank

#19 Recursion: Davis' Staircase

www.hackerrank.com

1 o 2 or 3段を一度に登れる人間が、n段の階段を登る際に、何通りの登り方が存在するか計算する問題。

以下のような入力が与えられる。

3
1
3
7

最初の行が階段の数。2行目以下は、階段のステップ数。 それぞれの階段について、何通りの登り方があるかを出力する。

上記入力の場合、出力は以下となる。

1
4
44

solution

再帰関数を使って解く。これもメモ化をすることでテストケースをパスすることができた。 以下rubyでの解。

#!/bin/ruby

class Solution
    
    def initialize(n, stepsATime)
        @steps, @stepsATime, @memo = n, stepsATime, []
    end
    
    def climbingWays(current = 0)
        return @memo[current] if @memo[current]
        return 0 if current > @steps
        return 1 if current == @steps
        
        ways = 0
        @stepsATime.each do |v|
            ways += climbingWays(current + v)
        end
        return @memo[current] = ways
    end
end

input = $stdin.read.split("\n").map(&:to_i)
input.shift.times do
    puts Solution.new(input.shift, [1,2,3]).climbingWays
end

github.com

再帰とは

再帰 - Wikipedia