板子题

/*
 * @Author: YMYS
 * @Date: 2024-12-17 08:55:40
 * @LastEditTime: 2024-12-17 09:56:33
 * @FilePath: \VScode-C&C++-Coding\Acwing\算法提高课\1.动态规划\1.数字三角形模型\1.摘花生.cpp
 * @URL:https://www.acwing.com/problem/content/1017/
 * @Description: 1015. 摘花生
 */
#include<bits/stdc++.h>

using namespace std;

const int N = 110;

int r,c;
int f[N][N], dp[N][N];

int T;
void solve(){
    cin>>r>>c;//r行c列

    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            cin>>f[i][j];
        }
    }

    //先把最左列和最上行弄好
    for(int i=1;i<=r;i++) dp[i][1] = dp[i-1][1] + f[i][1];
    for(int i=1;i<=c;i++) dp[1][i] = dp[1][i-1] + f[1][i];

    //然后按行开始遍历
    for(int i=2;i<=r;i++){
        for(int j=2;j<=c;j++){
            dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + f[i][j];
        }
    }

    cout<<dp[r][c]<<endl;
}

int main()
{
#ifdef ABC
    freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\in.in", "r", stdin);
    freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\out.out", "w", stdout);
#endif
    cin>>T;
    while(T--){
        solve();
    }

    return 0;
}