LIS：最長増加部分列
数列から「飛ばし飛ばしで選んだ増加列」のうち 一番長いものを、各要素の答えを積み上げて求めます。
計算ステップ（要素を 1 つずつ処理）
0
計算済み（数字＝dp 値）
計算中の要素
最長増加部分列
—
数列の中から、順序を保ちつつ 左から右へ増えていくように選んだ部分列が増加部分列。その最長のものが LIS です。
各要素は、自分より前にある自分より小さい要素のうち
dp[i] ＝「i 番目の要素で終わる LIS の長さ」。各要素は、自分より前にある自分より小さい要素のうち
dp が最大のものに乗っかる：
dp[i] = 1 + max(dp[j] | j<i, a[j]<a[i])
いま処理している要素
ここが DP の本質
- 「数列全体の LIS」を 「各要素で終わる LIS」という n 個の部分問題に分解。
- 各要素は すでに解いた前の要素の答え（dp 値）を再利用するだけ。全組合せを試さない。
- 「誰に乗ったか」を覚えておけば、最長の答えから逆にたどって LIS の中身を復元できる。