2.1015. 摘花生 - AcWing题库

定义dp数组 => dp[N][N]的含义就是 => 走到坐标为n,n最多能拿的花生数量
第一行第一列每一个位置能拿的花生数量都是固定的,我们先初始化好
然后后面每一个位置的最大值就能从左或者是上推导出来

#include<iostream>

using namespace std;
const int N = 110;
int dp[N][N];

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

    while (t--) {
        int r, c;
        //花生行数和列数
        cin >> r >> c;
        //每一个位置有多少个花生
        for (int i = 1; i <= r; i++) {
            for (int j = 1; j <= c; j++) {
                cin >> dp[i][j];
            }
        }

        //初始化行列,第一行第一列能拿的花生数都是固定的
        for (int i = 2; i < r; i++)dp[0][i] += dp[0][i - 1];
        for (int i = 2; i < c; i++)dp[i][0] += dp[i - 1][0];

        for (int i = 1; i <= r; i++) {
            for (int j = 1; j <= c; j++) {
                dp[i][j] += max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        cout << dp[r][c]<<endl;
    }
    return 0;
}