蓝桥杯方格取数动态规划-蒲公英云

蓝桥杯方格取数动态规划

题目描述
设有NN的方格图(N< =10),我们将其中的某些方格中填入正整数,而其他的方格中则放入数字0。
某人从图的左上角的A 点(1,1)出发，可以向下行走，也可以向右走，直到到达右下角的B点(N,N)。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。
此人从A点到B 点共走两次，试找出2条这样的路径，使得取得的数之和为最大。
输入
输入的第一行为一个整数N（表示NN的方格图），接下来的每行有三个整数，前两个表示位置，第三个数为该位置上所放的数。一行单独的0表示输入结束。
输出
只需输出一个整数，表示2条路径上取得的最大的和。
样例输入
8
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21
5 6 4
6 3 15
7 2 14
0 0 0
样例输出
67

一个人走两次，相当于两个人走一次，无非是走到同一格时只加一次，这里要知道每次都会让他们走，不存在一个人先到一个点一个人后到，只可能同时到达，所有不需要标记这个点是否走过

算法一 DFS(超时,这里分析一下时间复杂度，每个人的方案数是2^(n * n),每次计算len需要n，最坏复杂度就是2^100 * 10 显然超时

void dfs(int x1,int y1,int x2,int y2,int len)
{
    if(x1==x2&&y1==y2){
        len+=g[x1][y1];
    }
    else{
        len+=g[x1][y1]+g[x2][y2];
    }
    if(len>max_len){
        max_len=len;
    }
    if(x1+1<=n&&x2+1<=n){//都向下
        dfs(x1+1,y1,x2+1,y2,len);        
    }
    if(x1+1<=n&&y2+1<=n){//向下，向右
        dfs(x1+1,y1,x2,y2+1,len);
    }
    if(y1+1<=n&&x2+1<=n){//向右，向下
        dfs(x1,y1+1,x2+1,y2,len);
    }
    if(y1+1<=n&&y2+1<=n){
        dfs(x1,y1+1,x2,y2+1,len);
    }
}

算法二 DP(一般递归搜索超时，可以用动态规划，它直接记录一个集合的最大值，不会去花费多余时间去计算集合内每个方案的值

for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            for(int k=1;k<=n;++k){
                for(int m=1;m<=n;++m){
                    //当前状态由四个状态转移而来,左左，左上，上左，上上
                    int max1=max(f[i-1][j][k-1][m],f[i-1][j][k][m-1]);
                    int max2=max(f[i][j-1][k-1][m],f[i][j-1][k][m-1]);
                    if(i==k&&j==m){
                        f[i][j][k][m]=max(max1,max2)+g[i][j];
                    }
                    else{
                        f[i][j][k][m]=max(max1,max2)+g[i][j]+g[k][m];
                    }
                }
            }
        }
    }