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

4670 ワード
ダイナミックプログラミング 分割征服 復帰する テキストリンク
質問する
  • 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))
    Linuxインストール操作redis
    [白俊]10998号:A×B (JAVA)