$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

结论： $f[i][j]=\max(f[i-1][j],\ f[i][j-1])+w[i][j]$

思路：

• $1. 状态表示$
  $集合：从\ (1,1)\ 走到\ (i,j)\ 的所有路线$
  $属性：\max$

• $2. 状态转移$
  $从\ (i,j)\ 上方走来：f[i][j]=f[i-1][j]+w[i][j]$
  $从\ (i,j)\ 左方走来：f[i][j]=f[i][j-1]+w[i][j]$

• $3. 滚动数组$
  $由于\ f[i][j]\ 只需用到当前层和上一层，则结论可转化为：f[j]=\max(f[j],\ f[j-1])+w[i][j]$

完整代码1

#include<bits/stdc++.h>

using namespace std;

const int N = 110;

int n,m;
int w[N][N];
int f[N][N]; //从(1,1)走到(i,j)所有路线中的最大值

int main()
{
    int T;
    cin>>T;

    while(T--)
    {
        cin>>n>>m;

        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                cin>>w[i][j];

        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                f[i][j]=max(f[i-1][j],f[i][j-1])+w[i][j];

        cout<<f[n][m]<<endl; //从(1,1)走到(n,m)所有路线中的最大值
    }

    return 0;
}

完整代码2

#include<bits/stdc++.h>

using namespace std;

const int N = 110;

int n,m;
int w[N][N];
int f[N]; //从(1,1)走到(i,j)所有路线中的最大值

int main()
{
    int T;
    cin>>T;

    while(T--)
    {
        //多组测试数据需要初始化
        memset(f,0,sizeof f);

        cin>>n>>m;

        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                cin>>w[i][j];

        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++) //保证了 f[j-1] 是 f[i][j-1]
                f[j]=max(f[j],f[j-1])+w[i][j];

        cout<<f[m]<<endl; //从(1,1)走到(n,m)所有路线中的最大值
    }

    return 0;
}