動的計画法の核心：状態の定義と状態遷移方程式の定義
他の一般的な重複部分問題、無後効性、最適部分構造は、これら二つの核心内容に基づいています。
上記の状態遷移方程式では、等式の右辺は左辺の または より大きい下付きの値を使用しない、これは「無後効性」の一般的な数学的定義です。この定義に合致する状態定義は、「最適部分構造」の性質を持つと言えます。動的計画法において私たちが行うべきことは、この「最適部分構造」を見つけることです。
状態と状態遷移方程式の定義過程において、「最適部分構造」を満たすことは暗黙の条件です（そうでなければ定義できません）。
注意すべきは、ある問題には複数の異なる状態定義と状態遷移方程式の定義が存在する可能性があり、後効性のある定義が存在しても、その問題が動的計画法に適用できないわけではありません。これは他のいくつかの回答に見られる論理的誤解でもあります：
動的計画法は「最適部分構造」に合致する状態と状態遷移方程式の定義を探し、見つけた後は「メモ化を用いた再帰式の解法」で解決できます。そして見つけた定義こそが動的計画法の本質です。
各段階には一つの状態のみ -> 再帰；
各段階の最適状態は前の段階の最適状態から得られる -> 貪欲法；
各段階の最適状態は以前のすべての段階の状態の組み合わせから得られる -> 探索；
各段階の最適状態は以前のある段階のあるいくつかの状態から直接得られ、以前のその状態がどのように得られたかは関係ない -> 動的計画法。
各段階の最適状態が以前のある段階のあるいくつかの状態から直接得られるこの性質を最適部分構造と呼びます；
以前のその状態がどのように得られたかは関係ない、この性質を無後効性と呼びます。
補足： 実際、動的計画法における最適状態の言い方は誤解を招くことがあります。最適状態を計算するだけで良いと思われがちですが、LIS 問題は確かにそうで、遷移時には各段階で「選択」した状態のみが使用されます。しかし実際には、問題によっては各段階のすべての状態から最適値を計算し、その最適値に基づいて最適状態を見つける必要があります。例えば、ナップサック問題では、前の 個の袋（段階）で容量が のとき（状態）に最大価値を計算する必要があります。そして最後の段階のすべての状態の中から最適値を見つけます。