LCIS最長公共上升子序列

題解：https://blog.csdn.net/weixin_50624971/article/details/116892236

概括： 決策優化DP

考慮LCS可以寫成 $O(n^4)$ 的如果我們把狀態設為 $f[i,j]$ 表示考慮到 $a[i],b[j]$ 位置并且滿足$A[i]=B[j]$

為了滿足上升性質，我們強點 $B[j]$ 是當前所選的子序列的結尾，轉移時:

$$f[i,j]=max(f[i?1,k])+1(B[k]<B[j],k<j)$$

$$f[i,j]=f[i?1,j]$$

然后考慮第一種轉移，當 $i$ 不變 $j$ 單增的時候，對于所有可以轉移到 $j$ 一定有可選擇的 $k$ 集合是只進不出的