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 = …
アリ本にのっていたLISを全探索,メモ化でも解いたので覚え書き LISは与えられた配列をaとするとi>jかつa[i]>a[j]を満たす部分列のこと DPバージョン dp[i]はiより前のjの中で制約(i>j かつ a[i]>a[j])を満たすdp[j]の一番大きい値の+1となる. 例えば,a = …