最长上升子序列(LIS) + 最长下降子序列(LDS) 模板题. dp[i] 定义的是以A[i]为最后一个元素的最长上升(下降)子序列.

这题和方格取数一样, 都是2d的dp问题.

给一个2d矩阵, 里面有数字, 求取两个线上的数字,使得和最大, 只能往下和右走. 这个题我开始以为是greedy, 直接取一次, 再取一次就可以了, 然后感觉是不对的, 因为第一次走如果取了最大的值, 肯定会走过一些不是最大的值的路径, 而这些路径上的值是否就一定没有包含次大的值呢? 这个是不知道的. 所以要同时走才可以. 因为是同时, 相当于两个人在走A: (i1, j1),B: (i2,j2), 那么应该有 2*2四种情况. 所以应该是4维dp..然后看了讨论里,用的是压缩一维的方法, 即: 因为是n*n这么大的个子, 而且还只能往下往右走, 那么最多的步数就是2*n. 那么, 设k为当前步数, 就可以通过i找到j, 因为i+j=k, 比如极限情况下, 先走右到头然后下到头, 就是i=n, k=2*n, j = k-i = 2*n – n = n, 这样可以压缩一维, 四维变成三维 还有, 当计算数字的时候,如果两个人在同一格, 应该只取一次. 其他情况取各自格上的数.

给一个2d矩阵, 只能往下往右走, 每个格上有数字, 求最大能拿多少数字.