一个关于最长公共上升子序列的dp做法求hack
  • 板块学术版
  • 楼主Y2y7m
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/9/6 22:38
  • 上次更新2023/10/27 12:22:29
查看原帖
一个关于最长公共上升子序列的dp做法求hack
377440
Y2y7m楼主2022/9/6 22:38

求两个数组(元素个数分别为n,m)的最长公共上升子序列

定义: dpi,j(ai=bj)dp_{i,j}(a_i=b_j) 为以 aia_i 为结尾的最长公共上升子序列的长度(当 aia_i 不等于 bjb_j 时不存在)。

状态转移是:

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))

答案即为:max(dpi,j(1<=i<=n,1<=j<=m))max(dp_{i,j(1<=i<=n,1<=j<=m)})

求hack(时间复杂度不用考虑)

latex不太熟练,求各位大佬将就着看吧

2022/9/6 22:38
加载中...