给定一个m行n列的矩阵，从左上角开始每次只能向右或者向下移动，最后到达右下角的位置，路径上的所有数字累加起来作为这条路径的路径和。编写一个实验程序求所有路径和中的最小路径和。例如，以下矩阵中的路径1->3->1->0->6->1->0是所有路径中路径和最小的，返回结果是12： 1 3 5 9 8 1 3 4 5 0 6 1 8 8 4 0 Input 输入第一行为m，n的值，0<m,n<100。接下来是m行，每行n个整数，代表一个m行n列的矩阵。 Output 输出为1行，为最小路径和。c++代码

以下是C++的实现：

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

int main() {
    int m, n;
    cin >> m >> n;
    vector<vector<int>> matrix(m, vector<int>(n));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> matrix[i][j];
        }
    }

    vector<vector<int>> dp(m, vector<int>(n));
    dp[0][0] = matrix[0][0];

    // 初始化第一行和第一列
    for (int i = 1; i < m; i++) {
        dp[i][0] = dp[i-1][0] + matrix[i][0];
    }
    for (int j = 1; j < n; j++) {
        dp[0][j] = dp[0][j-1] + matrix[0][j];
    }

    // 递推计算dp数组
    for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++) {
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + matrix[i][j];
        }
    }

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

这个算法的时间复杂度为O(mn)，空间复杂度也是O(mn)。