ganmacs https://blog.hatena.ne.jp/ganmacs/ memo-mode https://ganmacs.hatenablog.com/ Java アルゴリズム アリ本にのっていたLISを全探索，メモ化でも解いたので覚え書き LISは与えられた配列をaとするとi>jかつa[i]>a[j]を満たす部分列のこと DPバージョン dp[i]はiより前のjの中で制約(i>j かつ a[i]>a[j])を満たすdp[j]の一番大きい値の+1となる． 例えば，a = {4, 2, 12, 3, 1, 5, 8, 10, 3, 9, 2, 11}でi=5のとき jの範囲は0<=j<5までなので，dp[0<=j<5]のなかで制約を満たす一番大きい値+1がdp[5]の値となる つまり，今回の場合はa[5]=5なので制約を満たすのはdp[j=3] (a[5] > a[3]… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fganmacs.hatenablog.com%2Fentry%2F2014%2F02%2F08%2F230140" title="LIS(最長増加部分列)を全探索，メモ化でといた - memo-mode" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2014-02-08 23:01:40 rich https://ganmacs.hatenablog.com/entry/2014/02/08/230140 1.0 100%