也是看了题解后才有的思路,但是大佬们好像没有讲怎么实现的去重(也可能是太容易想了?)
设人A坐标为(i,j),人B坐标为(k,l)
设四维数组f[i][j][k][l]表示当A走到(i,j)点,B走到(k,l)点时,两个人走过的所有路程和中最大的那个和。
因为A,B可以往右走,也可以往下走,所以f[i][j][k][l]是从2x2=4个地方中的最大的一个走过来的,即f[i][j][k][l]=max(max(f[i-1][j][k-1][l],f[i][j-1][k][l-1]),max(f[i][j-1][k-1][l],f[i-1][j][k][l-1]
两人的步数是同步的,若两人的坐标相同,那么对应的f不会赋值,而对每一个有值的f而言,一定是由若干个同样有值的f走过来的。所以每一个有值的f对应的两人路线一定是不会重复的。如此扩散,最后的结果(两人走的路线)也一定是不会重复的。