题目详情：有n*n个格子，每个格子里有正数或者0，从最左上角往最右下角走，只能向下和向右，一共走两次（即从左上角走到右下角走两趟），把所有经过的格子的数加起来，求最大值SUM，且两次如果经过同一个格子，则最后总和SUM中该格子的计数只加一次。
题目来源：此题是去年2013年搜狗的校招笔试题。
程序代写官网请进入--》》网上淘宝代写请进入--》》
解法一、直接搜索
@西芹_new，一共搜（2n-2）步，每一步有四种走法，考虑不相交等条件可以剪去很多枝，代码如下：
- //copyright@西芹_new 2013
- #include "stdafx.h"
- #include <iostream>
- using namespace std;
- #define N 5
- int map[5][5]={
- {2,0,8,0,2},
- {0,0,0,0,0},
- {0,3,2,0,0},
- {0,0,0,0,0},
- {2,0,8,0,2}};
- int sumMax=0;
- int p1x=0;
- int p1y=0;
- int p2x=0;
- int p2y=0;
- int curMax=0;
- void dfs( int index){
- if( index == 2*N-2){
- if( curMax>sumMax)
- sumMax = curMax;
- return;
- }
- if( !(p1x==0 && p1y==0) && !(p2x==N-1 && p2y==N-1))
- {
- if( p1x>= p2x && p1y >= p2y )
- return;
- }
- //right right
- if( p1x+1<N && p2x+1<N ){
- p1x++;p2x++;
- int sum = map[p1x][p1y]+map[p2x][p2y];
- curMax += sum;
- dfs(index+1);
- curMax -= sum;
- p1x--;p2x--;
- }
- //down down
- if( p1y+1<N && p2y+1<N ){
- p1y++;p2y++;
- int sum = map[p1x][p1y]+map[p2x][p2y];
- curMax += sum;
- dfs(index+1);
- curMax -= sum;
- p1y--;p2y--;
- }
- //rd
- if( p1x+1<N && p2y+1<N ) {
- p1x++;p2y++;
- int sum = map[p1x][p1y]+map[p2x][p2y];
- curMax += sum;
- dfs(index+1);
- curMax -= sum;
- p1x--;p2y--;
- }
- //dr
- if( p1y+1<N && p2x+1<N ) {
- p1y++;p2x++;
- int sum = map[p1x][p1y]+map[p2x][p2y];
- curMax += sum;
- dfs(index+1);
- curMax -= sum;
- p1y--;p2x--;
- }
- }
- int _tmain(int argc, _TCHAR* argv[])
- {
- curMax = map[0][0];
- dfs(0);
- cout <<sumMax-map[N-1][N-1]<<endl;
- return 0;
- }
解法二、动态规划
上述解法一的搜索解法是的时间复杂度是指数型的，如果是只走一次的话，是经典的dp。
2.1、DP思路详解
故正如@绿色夹克衫所说：此题也可以用动态规划求解，大概思路就是同时DP 2次所走的状态。
1、先来分析一下这个问题，为了方便讨论，先对矩阵做一个编号，且以5*5的矩阵为例（给这个矩阵起个名字叫M1）：
M10 1 2 3 41 2 3 4 52 3 4 5 63 4 5 6 74 5 6 7 8 从左上(0)走到右下(8)共需要走8步（2*5-2）。为了方便讨论，我们设所走的步数为s。因为限定了只能向右和向下走，因此无论如何走，经过8步后（s = 8)都将走到右下。而DP的状态也是依据所走的步数来记录的。 再来分析一下经过其他s步后所处的位置，根据上面的讨论，可以知道：
- 经过8步后，一定处于右下角(8)；
- 那么经过5步后(s = 5)，肯定会处于编号为5的位置；
- 3步后肯定处于编号为3的位置；
- s = 4的时候，处于编号为4的位置，此时对于方格中，共有5（相当于n）个不同的位置，也是所有编号中最多的。
故推广来说，对于n*n的方格，总共需要走2n - 2步，且当s = n - 1时，编号为n个，也是编号数最多的。
如果用DP[s,i,j]来记录2次所走的状态获得的最大值，其中s表示走s步，i，和j分别表示在s步后第1趟走的位置，和第2趟走的位置。 2、为了方便讨论，再对矩阵做一个编号（给这个矩阵起个名字叫M2）：M20 0 0 0 01 1 1 1 12 2 2 2 23 3 3 3 34 4 4 4 4把之前定的M1矩阵也再贴下：
M1 0 1 2 3 41 2 3 4 52 3 4 5 63 4 5 6 74 5 6 7 8 我们先看M1，在经过6步后，肯定处于M1中编号为6的位置。而M1中共有3个编号为6的，它们分别对应M2中的2 3 4。故对于M2来说，假设第1次经过6步走到了M2中的2，第2次经过6步走到了M2中的4，DP[s,i,j] 则对应 DP[6,2,4]。由于s = 2n - 2,0 <= i<= <= j <= n，所以这个DP共有O(n^3)个状态。M10 1 2 3 41 2 3 4 52 3 4 5 63 4 5 6 74 5 6 7 8 再来分析一下状态转移，以DP[6,2,3]为例(就是上面M1中加粗的部分)，可以到达DP[6,2,3]的状态包括DP[5,1,2]，DP[5,1,3]，DP[5,2,2]，DP[5,2,3]。3、下面，我们就来看看这几个状态：DP[5,1,2]，DP[5,1,3]，DP[5,2,2]，DP[5,2,3]，用加粗表示位置DP[5,1,2] DP[5,1,3] DP[5,2,2] DP[5,2,3] （加红表示要达到的状态DP[6,2,3]）
0 1 2 3 4 0 1 2 3 4 0 1 2 3 4 0 1 2 3 41 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 52 3 4 5 6 2 3 4 5 6 2 3 4 5 6 2 3 4 5 63 4 5 6 7 3 4 5 6 7 3 4 5 6 7 3 4 5 6 74 5 6 7 8 4 5 6 7 8 4 5 6 7 8 4 5 6 7 8 因此：DP[6,2,3] = Max(DP[5,1,2] ，DP[5,1,3]，DP[5,2,2]，DP[5,2,3]) + 6,2和6,3格子中对应的数值 （式一）
上面（式一）所示的这个递推看起来没有涉及：“如果两次经过同一个格子，那么该数只加一次的这个条件”，讨论这个条件需要换一个例子，以DP[6,2,2]为例：DP[6,2,2]可以由DP[5,1,1]，DP[5,1,2]，DP[5,2,2]到达，但由于i = j，也就是2次走到同一个格子，那么数值只能加1次。
所以当i = j时，DP[6,2,2] = Max(DP[5,1,1]，DP[5,1,2]，DP[5,2,2]) + 6,2格子中对应的数值 （式二）
4、故，综合上述的（式一），（式二）最后的递推式就是
if(i != j)DP[s, i ,j] = Max(DP[s - 1, i - 1, j - 1], DP[s - 1, i - 1, j], DP[s - 1, i, j - 1], DP[s - 1, i, j]) + W[s,i] + W[s,j]elseDP[s, i ,j] = Max(DP[s - 1, i - 1, j - 1], DP[s - 1, i - 1, j], DP[s - 1, i, j]) + W[s,i]其中W[s,i]表示经过s步后，处于i位置，位置i对应的方格中的数字。
复杂度分析：状态转移最多需要统计4个变量的情况，看做是O(1)的。共有O(n^3)个状态，所以总的时间复杂度是O(n^3)的。空间上可以利用滚动数组优化，由于每一步的递推只跟上1步的情况有关，因此可以循环利用数组，将空间复杂度降为O(n^2)。
2.2、DP方法实现
OK，上述这个方法可能不算最优解法，但相对比较容易想一些。
为了便于实现，我们认为所有不能达到的状态的得分都是负无穷，参考代码如下：
- //copyright@caopengcs 2013
- const int N = 202;
- const int inf = 1000000000; //无穷大
- int dp[N * 2][N][N];
- bool isValid(int step,int x1,int x2,int n) { //判断状态是否合法
- int y1 = step - x1, y2 = step - x2;
- return ((x1 >= 0) && (x1 < n) && (x2 >= 0) && (x2 < n) && (y1 >= 0) && (y1 < n) && (y2 >= 0) && (y2 < n));
- }
- int getValue(int step, int x1,int x2,int n) { //处理越界 不存在的位置 给负无穷的值
- return isValid(step, x1, x2, n)?dp[step][x1][x2]:(-inf);
- }
- //状态表示dp[step][i][j] 并且i <= j, 第step步 两个人分别在第i行和第j行的最大得分 时间复杂度O(n^3) 空间复杂度O(n^3)
- int getAnswer(int a[N][N],int n) {
- int P = n * 2 - 2; //最终的步数
- int i,j,step;
- //不能到达的位置 设置为负无穷大
- for (i = 0; i < n; ++i) {
- for (j = i; j < n; ++j) {
- dp[0][i][j] = -inf;
- }
- }
- dp[0][0][0] = a[0][0];
- for (step = 1; step <= P; ++step) {
- for (i = 0; i < n; ++i) {
- for (j = i; j < n; ++j) {
- dp[step][i][j] = -inf;
- if (!isValid(step, i, j, n)) { //非法位置
- continue;
- }
- //对于合法的位置进行dp
- if (i != j) {
- dp[step][i][j] = max(dp[step][i][j], getValue(step - 1, i - 1, j - 1, n));
- dp[step][i][j] = max(dp[step][i][j], getValue(step - 1, i - 1, j, n));
- dp[step][i][j] = max(dp[step][i][j], getValue(step - 1, i, j - 1, n));
- dp[step][i][j] = max(dp[step][i][j], getValue(step - 1, i, j,n));
- dp[step][i][j] += a[i][step - i] + a[j][step - j]; //不在同一个格子，加两个数
- }
- else {
- dp[step][i][j] = max(dp[step][i][j], getValue(step - 1, i - 1, j - 1, n));
- dp[step][i][j] = max(dp[step][i][j], getValue(step - 1, i - 1, j, n));
- dp[step][i][j] = max(dp[step][i][j], getValue(step - 1, i, j, n));
- dp[step][i][j] += a[i][step - i]; // 在同一个格子里，只能加一次
- }
- }
- }
- }
- return dp[P][n - 1][n- 1];
- }
2.3、DP实现优化版
以上代码的复杂度空间复杂度是O(n^3)，稍微想一下可以知道我们在推算dp[step]的时候 只有到了dp[step - 1]，所以第一维，我们只开到2就可以了。就是step为奇数时，我们都用dp[1][i][j]表示状态，step为偶数我们都用dp[0][i][j]表示状态，这样我们只需要O(n^2)的空间，这就是滚动数组的方法。滚动数组写起来并不复杂，只需要对上面的代码稍作修改即可，优化后的代码如下：
- //copyright@caopengcs 8/24/2013
- int dp[2][N][N];
- bool isValid(int step,int x1,int x2,int n) { //判断状态是否合法
- int y1 = step - x1, y2 = step - x2;
- return ((x1 >= 0) && (x1 < n) && (x2 >= 0) && (x2 < n) && (y1 >= 0) && (y1 < n) && (y2 >= 0) && (y2 < n));
- }
- int getValue(int step, int x1,int x2,int n) { //处理越界 不存在的位置 给负无穷的值
- return isValid(step, x1, x2, n)?dp[step % 2][x1][x2]:(-inf);
- }
- //状态表示dp[step][i][j] 并且i <= j, 第step步 两个人分别在第i行和第j行的最大得分 时间复杂度O(n^3) 使用滚动数组 空间复杂度O(n^2)
- int getAnswer(int a[N][N],int n) {
- int P = n * 2 - 2; //最终的步数
- int i,j,step,s;
- //不能到达的位置 设置为负无穷大
- for (i = 0; i < n; ++i) {
- for (j = i; j < n; ++j) {
- dp[0][i][j] = -inf;
- }
- }
- dp[0][0][0] = a[0][0];
- for (step = 1; step <= P; ++step) {
- for (i = 0; i < n; ++i) {
- for (j = i; j < n; ++j) {
- dp[step][i][j] = -inf;
- if (!isValid(step, i, j, n)) { //非法位置
- continue;
- }
- s = step % 2; //状态下表标
- //对于合法的位置进行dp
- if (i != j) {
- dp[s][i][j] = max(dp[s][i][j], getValue(step - 1, i - 1, j - 1, n));
- dp[s][i][j] = max(dp[s][i][j], getValue(step - 1, i - 1, j, n));
- dp[s][i][j] = max(dp[s][i][j], getValue(step - 1, i, j - 1, n));
- dp[s][i][j] = max(dp[s][i][j], getValue(step - 1, i, j,n));
- dp[s][i][j] += a[i][step - i] + a[j][step - j]; //不在同一个格子，加两个数
- }
- else {
- dp[s][i][j] = max(dp[s][i][j], getValue(step - 1, i - 1, j - 1, n));
- dp[s][i][j] = max(dp[s][i][j], getValue(step - 1, i - 1, j, n));
- dp[s][i][j] = max(dp[s][i][j], getValue(step - 1, i, j, n));
- dp[s][i][j] += a[i][step - i]; // 在同一个格子里，只能加一次
- }
- }
- }
- }
- return dp[P % 2][n - 1][n- 1];
- }