前言
这一道题不太难，怎么表现呢？
告诉你吧，
萌新写的代码长度25行
。
直入主题
首先呢，我在这里先不直接讲最强大的二维DP，
先从四维开始吧：
基础：
四维DP，
时间、空间复杂度都为 O(n
4
)
用f[i][j][x][y]表示
第一张纸条传到(i,j),
第二张纸条传到(x,y)
它们累计下来的好心程度和。
对于每一步呢，
分别有四种情况
：
1.第一张纸条向下传，第二张纸条向下传；
2.第一张纸条向下传，第二张纸条向右传；
3.第一张纸条向右传，第二张纸条向下传；
4.第一张纸条向右传，第二张纸条向右传；
F[i][j]=max(F[i-1][j][x-1][y] ,F[i-1][j][x][y-1] ,F[i][j-1][x-1][y] ,F[i][j-1][x][y-1])+a[i][j]+a[x][y];
1
那么如何
判重
呢？
其实可以不判，只要你想办法使它没有重复的情况就行了，
So for循环时我们限制y<x。
升级
三维DP，
时间复杂度O（n
3
)；空间复杂度多一倍；
我们可以发现每一张纸条每一步
要么只走右边，
要么只走下边，
2
所以i+j=x+y;于是我们DP每一步的情况
3
，
用i表示第一张纸往下走了多少步，因为枚举了k=i+j（就是走了多少步）所以可以用k-i来代替j；
第二张纸也同样可以用k和x表示出来坐标。因为枚举的是步数
4
所以呢，空间才会多一倍。
于是 F[k][i][x]=max(F[k-1][i][x]+F[k-1][i][x-1]+F[k-1][i-1][x]+F[k-1][i-1][x-1])；
Boss进阶：
最强大的二维DP，复杂度和三维一样，但空间少了很多
如果你对背包问题掌握得十分娴熟，你就能用背包思想来降维。怎么做到的呢？
我们从三维DP的状态转移式中发现它只和上一步有关系，
并只牵扯到x，x-1，没用到x+1；
所以我们从后向前推，这样你现在用的二维数组就是上一步的，对x进行覆盖也不会产生后效性。
Readers:这又如何去重呢？
Reply:其实和四维一样，你只需要保证 x > i 就行啦，因为这样就不会有重复情况出现，自然也就不需要去重啦。
萌新求赞!