レビュー ワークシートを調べて、動的計画法を使用して連鎖行列乗算の再帰関係を見つけるための助けを探していました。
M0M1…Mn - 1問題の逐語的説明:関連する次元シーケンスを持つ 連鎖行列積の最適な括弧の問題を考えてみましょう(d0, d1, … ,dn)。この問題の動的計画法解の基礎となる再帰関係、つまり、連鎖積 のすべての括弧にわたる乗算の最小数 mij の再帰関係を導出しますMiM1…Mj。初期状態を忘れないでください。
の公式が分かりましたM[i,j] (M[i,j] = M[i,k] + M[k+1,j] + pqr)。これには間違いなく再帰があります。しかし、どのように再帰関係を決定するのですか? これはすでに再帰関係ではありませんか？また、「関連次元空間」とはどういう意味ですか?