「動的計画法」の版間の差分

[[最適化問題]]に適用する場合、最低限一般的に、以下の2つが適用する問題に成立していないといけない<ref name="ai"/>。（厳密には成立しなくても動的計画法の定義は満たせる）

部分問題を解き、それを利用して、全体の最適化問題を解く戦略のため、部分構造最適性が動的計画法には必須要である。部分構造最適性の例として、[[最短経路問題]]では、A → B → C という最短経路において、A → B や B → C も最短経路でないといけない（このことは[[背理法]]により証明可能）。また、部分問題間が独立であるためには、部分問題で資源の共有があってはならない。最短経路問題では A → B と B → C で同じ辺が出現しないため（同じく背理法により証明可能）、資源の共有が発生していない。[[貪欲法]]においても厳密解を求めるのなら部分構造最適性は必要である。