蓝桥杯方格取数动态规划

朴灿烈づ我的快乐病毒、 2023-08-17 15:43 83阅读 0赞

> 题目描述  
> 设有N*N的方格图(N< =10),我们将其中的某些方格中填入正整数,而其他的方格中则放入数字0。  
> 某人从图的左上角的A 点(1,1)出发，可以向下行走，也可以向右走，直到到达右下角的B点(N,N)。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。  
> 此人从A点到B 点共走两次，试找出2条这样的路径，使得取得的数之和为最大。  
> 输入  
> 输入的第一行为一个整数N（表示N*N的方格图），接下来的每行有三个整数，前两个表示位置，第三个数为该位置上所放的数。一行单独的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];
                        }
                    }
                }
            }
        }

转载于:https://www.cnblogs.com/clear-love/p/11346929.html