过河卒算法

过河卒基本思想：利用动态规划转空间为时间，利用动态规划一般方法，把数据记录下来,同时走两条路线，只要不重合就好

#include <cstdio>

#include <iostream>

#include <cmath>

#include <cstring>

#define maxx(A,B,C,D) max(max(A,B),max(C,D))

using namespace std;

int m,n,heart[55][55],f[110][55][55];

int main()

{

    scanf("%d%d",&m,&n);

    for(int i = 1;i <= m;i++)

        for(int j = 1;j <= n;j++)

            scanf("%d",&heart[i][j]);

for(int k = 1;k <= n+m-2;k++)//k代表步数，这样就可以不用4维数组，减少一维

    for(int i = 1;i <= m && i <= k+1;i++)

        for(int j = 1;j <= m && j <= k+1;j++)

        {

            if(i == j && k != n+m-2) continue;

            f[k][i][j] = maxx(f[k-1][i-1][j],f[k-1][i][j-1],f[k-1][i-1][j-1],f[k-1][i][j])+ heart[i][k+2-i] + heart[j][k+2-j];//减少一维表示

        }

printf("%d",f[m+n-2][m][m]);

return 0;
}

第二种   为4维数组

//传纸条
#include<stdio.h>

int a[51][51] = {0};
// 好感度数组
int f[51][51][51][51] = {0};
// 动态规划数组，f[i][j][k][l] 表示从 (0, 0) 位置由两条不交叉的线路走到 (i, j)，(k, l) 位置时的最大好感度和

int max(int a, int b){
    return a > b ? a : b;
}

int main(){
    int m, n;
    scanf("%d%d", &m, &n);
    for(int i = 1; i <= m; ++i){
        for(int j = 1; j <= n; ++j){
            scanf("%d", &a[i][j]);
        }
    }
    // 开始循环解题
    for( i = 1; i <= m; ++i){
        for(int j = 1; j <= n; ++j){
            for(int k = 1; k <= m; ++k){
                for(int l = 1; l <= n; ++l){
                    // 还没到终点前不能走到同一个点，因此(i, j)不能等于(k, l)
    // 加上小于判断是因为当(i, j)跟(k, l)互换时，最大好感度值必定一样，不必重复计算,与上一个相比减少了运算次数
                    if((i < m || j < n) && i <= k && j <= l){
                        continue;
                    }
                    int num = 0;
                    // 两个点都由上走来的好感度
                    num = max(num, f[i - 1][j][k - 1][l]);
    // 第一个点由上走来，第二个点从左走来，并且两个来源点不重合时的好感度
                    if(i - 1 != k && j != l - 1){
                        num = max(num, f[i - 1][j][k][l - 1]);
                    }
    // 第一个点由左走来，第二个点从上走来，并且两个来源点不重合时的好感度
                    if(i != k - 1 && j - 1 != l){
                        num = max(num, f[i][j - 1][k - 1][l]);
                    }
                    // 两个点都由左走来的好感度
                    num = max(num, f[i][j - 1][k][l - 1]);
                    // 加上当前两点的好感度，即为走到这两点时的最大好感度和
                    f[i][j][k][l] = num + a[i][j] + a[k][l];
                }
            }
        }
    }
    // 输出由两条不交叉的线路走到右下角时的最大好感度和
    printf("%d\n", f[m][n][m][n]);
    return 0;
}