白駿9095号:1、2、3プラス

質問する

https://www.acmicpc.net/problem/9095

の整数Nを1、2、3の和として表す場合、可能な個数

を求める.
きろくてん

回帰/分割征服:分割、征服、結合の3つの段階はどのように問題に応用されますか?

現在の問題を同じ問題を処理する複数のローカル問題に分けます!

1,2,3の組み合わせで、1,2,3をベースキャビネットに設定し、

.

数量に基づく再帰構成

の「個数」を数え、すべてのケースを表示する必要はありません.

すべてのケースを習慣的に作成して、本当に

が必要かどうかを見てみましょう.

動的プログラミング

がf(4)値の計算を繰り返すと仮定し、保存して後でロードして

を使用します.
方法

現在の問題を同じ問題を処理する複数のローカル問題に分割する

f(1) = 1get_cases(1) >>> [[1]]

f(2) = 2get_cases(2) >>> [[1,1], [2]]

f(3) = 4get_cases(3) >>> [[1,1,1], [1,2], [2,1], [3]]

f(4) = f(3) + f(2) + f(1)

1+3表示=f(3)[[1] + c for c in [[1,1,1], [1,2], [2,1], [3]]] [[1] + c for c in get_cases(3)]

2+2、=f(2)[[2] + c for c in [[1,1], [2]]] [[2] + c for c in get_cases(2)]

3+1表示=f(1)[[3] + c for c in [[1]]] [[3] + c for c in get_cases(1)]

fn(5) = f(4) + f(3) + f(2) = { f(3) + f(2) + f(1) } + f(3) + f(2)

f(4)記憶値は、繰返し計算

を低減することができる.

fn(N) = f(N-1) + f(N-2) + f(N-3)

汎用

回答の提出

import sys
N = int(sys.stdin.readline())

results = {}

def fn(value):
    if value == 1: return 1
    if value == 2: return 2
    if value == 3: return 4
    if value in results: return results[value]
    total = fn(value-1) + fn(value-2) + fn(value-3)
    results[value] = total
    return total

for i in range(N):
    value = int(sys.stdin.readline())
    print(fn(value))