c++求解矩阵最小路径和问题。给定一个m行n列的矩阵,从左上角开始每次只能向右或者向下移动,最后到达右下角的位置,路径上的所有数字累加起来作为这条路径的路径和。编写一个程序求所有路径和中的最小路径和。

下面是C++代码实现：

#include <vector>
#include <algorithm>

using namespace std;

int minPathSum(vector<vector<int>>& matrix) {
    int m = matrix.size(), n = matrix[0].size();
    vector<vector<int>> dp(m, vector<int>(n, 0));
    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];
    }
    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];
        }
    }
    return dp[m-1][n-1];
}

时间复杂度为 O(mn)，空间复杂度为 O(mn)。