【正经题解】方格取数

这段代码通过动态规划求解从左上角到右下角的最大路径和。首先初始化一个二维数组 $dp$ ，表示从起点到达该位置的最大和。然后输入每个格子中的数字，接着使用动态规划递推计算最大和。最后输出右下角的最大和作为结果。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 105;
int dp[N][N];

int main() {
    int n, m;
    cin >> n >> m;

    // 初始化dp数组，表示从起点到达该位置的最大和
    memset(dp, 0, sizeof(dp));

    // 输入每个格子中的数字
    for (int i = 0; i < m; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        dp[x][y] = z;
    }

    // 动态规划计算最大和
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            dp[i][j] += max(dp[i - 1][j], dp[i][j - 1]);
        }
    }

    // 输出结果
    cout << dp[n][n] << endl;

    return 0;
}