求两个数组(元素个数分别为n,m)的最长公共上升子序列
定义: dpi,j(ai=bj)dp_{i,j}(a_i=b_j)dpi,j(ai=bj) 为以 aia_iai 为结尾的最长公共上升子序列的长度(当 aia_iai 不等于 bjb_jbj 时不存在)。
状态转移是:
dpi,j=max(1,max(dpi1,j1(ai1=bj1)(ai1<ai))dp_{i,j}=max(1,max(dp_{i_1,j_1(a_{i_1}=b_{j_1})}(a_{i_1}<a_i))dpi,j=max(1,max(dpi1,j1(ai1=bj1)(ai1<ai))
答案即为:max(dpi,j(1<=i<=n,1<=j<=m))max(dp_{i,j(1<=i<=n,1<=j<=m)})max(dpi,j(1<=i<=n,1<=j<=m))
求hack(时间复杂度不用考虑)
latex不太熟练,求各位大佬将就着看吧