はじめに この記事では動的計画法を使って100回後のダイパリメイクの名前を予測します。言語はpythonです。 動的計画法とは 動的計画法は前の状態から次の状態を計算することで計算量を落とすアルゴリズムです。 ダイパリメイクの命名では動的計画法が使用されており、ダイアモンドにブリリアンを、パールにシャイニングを追加することで次のリメイクの名前を決定している事がわかります。よって次のコードが書けます。 N = 101 dp = [['', ''] for _ in range(N)] dp[0] = ["ダイアモンド", "パール"] for i in range(N - 1): dp[i + …