ダイパキッズでもよくわかるDP(動的計画法)

はじめに

この記事では動的計画法を使って100回後のダイパリメイクの名前を予測します。言語はpythonです。

動的計画法とは

動的計画法は前の状態から次の状態を計算することで計算量を落とすアルゴリズムです。
ダイパリメイクの命名では動的計画法が使用されており、ダイアモンドにブリリアンを、パールにシャイニングを追加することで次のリメイクの名前を決定している事がわかります。

よって次のコードが書けます。

N = 101
dp = [['', ''] for _ in range(N)]
dp[0] = ["ダイアモンド", "パール"]
for i in range(N - 1):
    dp[i + 1][0] = "ブリリアント" + dp[i][0]
    dp[i + 1][1] = "シャイニング" + dp[i][1]
print("ダイアモンドの100回目のリメイクの名前は", dp[-1][0])
print("パールの100回目のリメイクの名前は", dp[-1][1])

実行結果は次のようになり100回目のリメイクの名前がわかります。

ダイアモンドの100回目のリメイクの名前は ブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントブリリアントダイアモンド
パールの100回目のリメイクの名前は シャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングパール
||<