【动态规划】求二维数组从左下到右上的最优路径

古城微笑少年丶 2022-08-09 00:58 150阅读 0赞

1.求二维数组从左下到右上的最优路径，使得路径和最大，并且只能向上或向下走。  
解析：求最短路径，路径和最优等都可以用动态规划做。  
dp\[i\]\[j\]表示到i，j坐标的最优路径。  
第一，确定初始条件。即向上向左的最优路径确定  
dp\[i,0\] = dp\[i-1,0\] + arr\[i\]\[0\] where j =0  
dp\[0,j\] = dp\[0,j-1\] + arr\[0\]\[j\] where i =0  
第二，根据初始条件，迭代出整个数组。  
dp\[i,j\] = max\{dp\[i+1,j\],dp\[i,j-1\]\} + arr\[i\]\[j\]  
第三，dp\[0,m\]即是最优路径的值。

//求从二维数组左下到右上的路径，最大值。
    //只可以向右向上走，二维数组值已给定。
    int getmax(int a[][5],int n)
    {
        int i,j,k,t;
        int tmp,rtn;
        int** ta = (int**)malloc(sizeof(int)*n*n);
        ta[0]=(int *)malloc(n*n*sizeof(int));  
        for(int i=1;i<n;i++)  
            ta[i]=ta[0]+i*n; 
    //------核心代码---------------------------------------------
        //第一阶段，为第二阶段的递推铺垫
        ta[n-1][0] = a[n-1][0];
        for (i=n-2,j=1;i>=0&&j<n;i--,j++) //求出（N，j）和（i，N）列的最大值
        {
            ta[n-1][j] = a[n-1][j] + ta[n-1][j-1];
            ta[i][0] = a[i][0] + ta[i+1][0];
        }
    
        //第二阶段
        for (i = n-2,j = 1;i>=0&&j<n;i--,j++)
        {
            for (k = j;k<n;k++)
            {
                tmp = ta[i+1][k] > ta[i][k-1]? ta[i+1][k]:ta[i][k-1];
                ta[i][k] = a[i][k] + tmp;
            }
            for(t=i;t>=0;t--)
            {
                tmp = ta[t+1][j] > ta[t][j-1]? ta[t+1][j]:ta[t][j-1];
                ta[t][j] = a[t][j] + tmp;
            }
        }
    //------核心代码--------------------------------------------
    
        for (i=0;i<5;i++)
        {
            for(j=0;j<5;j++)
            {
                cout << ta[i][j] << "  ";
            }
            cout << endl;
        }
    
        rtn = ta[0][n-1];
        delete []ta;ta = NULL;
        return rtn;
    }

测试用例：

void main()
    {
        int a[5][5];
        int i,j;
        for (i=0;i<5;i++)
        {
            for(j=0;j<5;j++)
            {
                a[i][j] = rand()%50;
            }
        }
        for (i=0;i<5;i++)
        {
            for(j=0;j<5;j++)
            {
                cout << a[i][j] << "  ";
            }
            cout << endl;
        }
    
        cout << getmax(a,5) << endl;
    
    }