题意概括

给定一个 m x n 的网格，每个格子里都包含一个非负整数。你需要找出一条从左上角到右下角的路径，使得这条路径上所有数字的总和最小。

移动规则:

• 在任何位置，每次只能选择 向下 或 向右 移动一步。

数据范围:

• 网格的行数和列数 $m, n$ 满足 $1 \le m, n \le 200$。
• 网格中的数字大小范围为 $[0, 100]$。

基础知识

这是一个经典的 动态规划 (Dynamic Programming, DP) 问题。由于路径的移动方向是固定的（只能向下或向右），这意味着我们到达一个点 (i, j) 的路径，必然经过 (i-1, j) 或 (i, j-1)。这种无后效性的特性是应用动态规划的理想场景。

动态规划三要素:

1. 状态定义: 我们定义一个二维 DP 数组 dp[i][j]，它的含义是：从起点 (0, 0) 出发，到达网格坐标 (i, j) 的所有可能路径中，数字总和最小的那条路径的和是多少。我们的最终目标就是求解 dp[m-1][n-1]。

2. 状态转移方程: 对于任意一个非边界的单元格 (i, j)，要想到达它，只有两种可能：

   • 从其上方的单元格 (i-1, j) 向下移动一步。
   • 从其左方的单元格 (i, j-1) 向右移动一步。 为了使得到达 (i, j) 的路径和最小，我们理应选择这两条来源路径中总和较小的那一条。因此，状态转移方程可以表示为：
   $$dp[i][j] = \text{grid}[i][j] + \min(dp[i-1][j], dp[i][j-1]) $$

3. 初始化 (边界条件):

   • 起点: dp[0][0] 就是左上角单元格本身的值，因为到达它只有一种方式。
   • 第一行: 对于第一行的任意单元格 (0, j)，它只能从左边的单元格 (0, j-1) 移动而来。所以 dp[0][j] = grid[0][j] + dp[0][j-1]。
   • 第一列: 同理，对于第一列的任意单元格 (i, 0)，它只能从上方的单元格 (i-1, 0) 移动而来。所以 dp[i][0] = grid[i][0] + dp[i-1][0]。

通过从上到下、从左到右的顺序填充整个 dp 数组，我们最终就能计算出 dp[m-1][n-1] 的值。

复杂度分析:

• 时间复杂度: 我们需要为 m x n 个单元格计算 dp 值，每次计算是常数时间，所以总时间复杂度为 $O(m \times n)$。
• 空间复杂度: 我们需要一个 m x n 大小的 dp 数组来存储中间状态，所以空间复杂度为 $O(m \times n)$。

C++ 解决方案

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void slv() {
    int m, n;
    cin >> m >> n;

    // 使用vector作为动态二维数组
    vector<vector<int>> dp(m, vector<int>(n, 0));

    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            int x;
            cin >> x;

            if (i == 0 && j == 0) {
                // 起点
                dp[i][j] = x;
            } else if (i == 0) {
                // 第一行，只能从左边来
                dp[i][j] = x + dp[i][j - 1];
            } else if (j == 0) {
                // 第一列，只能从上边来
                dp[i][j] = x + dp[i - 1][j];
            } else {
                // 一般情况，取左边和上边的较小值
                dp[i][j] = x + min(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    cout << dp[m - 1][n - 1] << endl;
}

int main() {
    // 关闭同步流，加速IO
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    slv();

    return 0;
}

/*
样例输入 1:
3 3
1 3 1
1 5 1
4 2 1

样例输出 1:
7

样例输入 2:
2 3
1 2 3
4 5 6

样例输出 2:
12
*/