本文共 3112 字，大约阅读时间需要 10 分钟。

格子取数问题

动态规划：

DP[step,i,j]表示的是第step步（每两步算一步）走到第i行和第j行（不需要知道列，因为走了step步，肯定走到的是step这个数，如下图所示）

例如：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 4 1 2 3 4 5    1 2 3 4 5    1 2 3 4 5    1 2 3 4 5 2 3 4 5 6    2 3 4 5 6    2 3 4 5 6    2 3 4 5 6

3 4 5 6 7    3 4 5 6 7    3 4 5 6 7    3 4 5 6 7 4 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格子中对应的数值                         （式二）

#include 
   
         #include 
    
     #include 
     
      using namespace std;    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];  }  int main(){    int map[N][N]={        {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}};   	cout<