DP とメモ化再帰の違いは？

本質的に同じです。メモ化再帰はトップダウンで自然に書け、DP テーブル（配列）はボトムアップで定数倍が速い傾向があります。複雑な状態遷移はメモ化、シンプルな漸化式は DP 配列が読みやすいことが多いです。

DP の状態の数え方が分かりません

「決めなければ次が決まらない情報」を全部状態にするのがコツです。例えばナップサックなら「現在の品物 i」と「残り容量 w」の 2 つで状態が決まります。状態が多くなりすぎたら DP は向かないかもしれません。

DP テーブルが直前の行しか参照していなければ、2 行分（または 1 行 + 一時変数）で十分です。フィボナッチは 2 変数で済み、Edit Distance や LCS も 2 行 DP に圧縮できます。空間計算量を O(n) から O(1) や O(n) に減らせることが多いです。

動的計画法に関する次の記述のうち、正しいもの はどれですか?

Kadane のアルゴリズム (最大部分配列和) は変数 2 つだけで O(n) 時間・O(1) 空間で解ける

Word Break では wordDict を配列のまま .includes / .indexOf で線形検索すべきだ

LIS の素朴な O(n^2) DP では dp[i] を 0 で初期化するのが正しい

編集距離 (Levenshtein) の二次元 DP は O(m + n) 時間で解ける

動的計画法に関する次の記述のうち、正しいもの はどれですか?

Kadane のアルゴリズム (最大部分配列和) は変数 2 つだけで O(n) 時間・O(1) 空間で解ける

Word Break では wordDict を配列のまま .includes / .indexOf で線形検索すべきだ

LIS の素朴な O(n^2) DP では dp[i] を 0 で初期化するのが正しい

編集距離 (Levenshtein) の二次元 DP は O(m + n) 時間で解ける