ダイパキッズでもよくわかるDP(動的計画法)
動的計画法とは
動的計画法は前の状態から次の状態を計算することで計算量を落とすアルゴリズムです。
ダイパリメイクの命名では動的計画法が使用されており、ダイアモンドにブリリアンを、パールにシャイニングを追加することで次のリメイクの名前を決定している事がわかります。
よって次のコードが書けます。
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回目のリメイクの名前は シャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングシャイニングパール ||<