[Python] ABC006 B

問題

B – トリボナッチ数列

参考

GeeksForGeeks Tribonacci Numbers

英語のサイトですが、トリボナッチ数列の普通の解き方->効率的な解き方のコードが一通りの言語で載っています。

回答

動的計画法

import sys
# input処理を高速化する
input = sys.stdin.readline


def main():
    N = int(input())

    dp = [0] * (N + 2)
    dp[0] = 0
    dp[1] = 0
    dp[2] = 1
    
    for i in range(3, N):
        num = dp[i - 3] + dp[i - 2] + dp[i - 1]
        dp[i] = num % 10007

    print(dp[N-1])
    
main()

メモ化再帰

PyPyでもTLE になってしまう。書けなかった。またいつか…。

import sys
# input処理を高速化する
input = sys.stdin.readline
# 許容する再帰処理の回数を変更
sys.setrecursionlimit(10**6+10)

def main():
    N = int(input())

    memo = [-1] * (N+1)
    def trib(n):
        if n == 0:
            return 0
        if n == 1:
            return 0
        if n == 2:
            return 1

        if memo[n] >= 0:
            return memo[n]
        num = trib(n-3) + trib(n-2) + trib(n-1)
        memo[n] = num % 10007
        return memo[n]

    print(trib(N-1))

main()