=begin
File: climbing_stairs_dfs.rb
Created Time: 2024-05-29
Author: Xuan Khoa Tu Nguyen (ngxktuzkai2000@gmail.com)
=end

### 探索 ###
def dfs(i)
  # dp[1] と dp[2] は既知なので返す
  return i if i == 1 || i == 2
  # dp[i] = dp[i-1] + dp[i-2]
  dfs(i - 1) + dfs(i - 2)
end

### 階段登り：探索 ###
def climbing_stairs_dfs(n)
  dfs(n)
end

### Driver Code ###
if __FILE__ == $0
  n = 9

  res = climbing_stairs_dfs(n)
  puts "#{n} 段の階段を上る方法は全部で #{res} 通り"
end