Dynamic Programming（動的計画法）
動的計画法は、以前に計算した結果（これまでの状態）をもとにして新たな状態を作り上げる「技術（アート）」です。プログラムで何らかの計算を行うとき、実行中に求められた過去の値を利用することがよくあります。フィボナッチ数列は動的計画法で計算できる代表的な例です:
たとえば、
fib(2) を求めるときは、すでに計算してある fib(1) と fib(0) を使います。すると fib(2) = 1 となります。次に fib(3) を求めるときは、先ほど計算した fib(2) と fib(1) を使って、fib(3) = fib(2) + fib(1) = 1 + 1 = 2 となります。同様に、fib(4) = fib(3) + fib(2) = 2 + 1 = 3、fib(5) = fib(4) + fib(3) = 3 + 2 = 5 と続いていきます。このようにループごとに、過去に求めた状態（今回の例では直前のフィボナッチ数）を使って現在の値を計算していきます。リストを使えば、次のように実装することが可能です:
n = ...
fib = [0, 1] # fib[0] = 0, fib[1] = 1
for i in range(2, n + 1):
fib.append(fib[i - 1] + fib[i - 2])
print(fib[n])もし
n = 5 ならこのプログラムは 5 を出力し、n = 7 なら 13 を出力します。このように、すでに計算済みの状態（値）を繰り返し利用しながら求めていく手法こそが動的計画法の本質です。
💡
Dynamic programming is a technique to construct the current state based on the previous states.
Challenge – Tribonacci numbers
フィボナッチ数列を扱っていたら飽きてしまい、代わりに Tribonacci 数列で遊んでみることにしました。Tribonacci 数列は次のように定義されます:
ここで、あなたの課題は
n 番目の Tribonacci 数を求めることです。Input
入力は整数
n（1 ≤ n ≤ 30）を 1 つ含みます。Output
出力は
n 番目の Tribonacci 数を表示してください。Examples
Input | Output |
2 | 1 |
4 | 2 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB