Ruby
yukicoder

An Ordinary Sequence

問題

解法

  • 単純にメモ化再帰だけで良いです。これは、n/x/y == n/y/x (== n/(x*y)) がどのような自然数に対しても成立するため、当然 n/3/5 == n/5/3 となるからです。
  • 証明は https://qiita.com/cielavenir/items/21a6711afd6be8c18c55 をご覧ください。

答案

$memo={0=>1}
def dfs(n)
    $memo[n]||=dfs(n/3)+dfs(n/5)
end
p dfs(gets.to_i)