エントリーの編集
エントリーの編集は全ユーザーに共通の機能です。
必ずガイドラインを一読の上ご利用ください。
[競プロ][Python]動的計画法 - Qiita
記事へのコメント0件
- 注目コメント
- 新着コメント
このエントリーにコメントしてみましょう。
注目コメント算出アルゴリズムの一部にLINEヤフー株式会社の「建設的コメント順位付けモデルAPI」を使用しています
- バナー広告なし
- ミュート機能あり
- ダークモード搭載
関連記事
[競プロ][Python]動的計画法 - Qiita
動的計画法とは 動的計画法(Dynamic Programming)は、対象となる問題を複数の部分問題に分割し、部分... 動的計画法とは 動的計画法(Dynamic Programming)は、対象となる問題を複数の部分問題に分割し、部分問題の計算結果を記録しながら解いていく手法です。 動的計画法は特定のアルゴリズムではなく、考え方です。 動的計画法を適用するには、以下の条件が成立する必要があります。 最適な部分構造(optimal substructure) 重複する部分問題(overlapping subproblems) 後付けなし 最適な部分構造(optimal substructure) 最適な部分構造は、部分問題と元の問題との関係を規定するものです。 動的計画法は問題の最適解を見つけること、つまり問題に対する多数の解の中から最適なものを見つけ出すことです。 問題の最適解は、その部分問題の最適解によって決定されます。 最適な部分構造は、以下の2条件が成立していることを指します。 部分問題も同じ最適化