题目描述

题目描述不再赘述，一道典型的二维dp，我的思考是要考虑每一步的“决策”是什么，也就是说我通过什么方法让这一步实现最优解进而获取整个题目的最优解，对于这道题而言，每一步的最大值取决于上一步的来源（来源于东还是南）。最后根据决策写出方程：dp[i][j]=max(dp[i-1][j],dp[i][j-1])+a[i][j];,这里要注意这一步是上一步来的，所以i-1/j-1

样例

输入样例：
2
2 2
1 1
3 4
2 3
2 3 4
1 6 5
输出样例：
8
16

算法1

#include<bits/stdc++.h>
using namespace std;
int T;
int n,m;
const int N=110;
int a[N][N];
int sum[N][N];
int main()
{
    cin>>T;
    while(T--)
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                cin>>a[i][j];
            }
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                sum[i][j]=max(sum[i-1][j],sum[i][j-1])+a[i][j];
            }
        }
        cout<<sum[n][m]<<endl;
    }
    return 0;
}