题解 | #矩阵的最小路径和#

这是一个典型的动态规划问题。

从最左上结点a[0][0]到当前结点a[i][j]的最短路径dp[i][j]只取决于dp[i - 1][j], dp[i][j - 1]和a[i][j]。

当然要特殊考虑一下i或j为0的情况。

递推式为：dp[i][j] =

1. min(dp[i - 1][j], dp[i][j - 1]) + a[i][j], i > 0 且 j > 0
2. dp[i - 1][j] + a[i][j], j = 0
3. dp[i][j - 1] + a[i][j], i = 0

class Solution {
public:
    vector<vector<int> > initDP(int rows, int cols)
    {
        vector<vector<int> > dp(rows);
        vector<int> v(cols);
        for (int i = 0; i < rows; i++)
        {
            dp[i] = v;
        }

        return dp;
    }
    
    int minPathSum(vector<vector<int> >& matrix) {
        if (matrix.empty() || matrix[0].empty())
        {
            return 0;
        }

        int rows = matrix.size();
        int cols = matrix[0].size();
        
        vector<vector<int> > dp = initDP(rows, cols);
        dp[0][0] = matrix[0][0];
        for (int i = 0; i < rows; i++)
        {
            for (int j = 0; j < cols; j++)
            {
                if (i > 0 && j > 0)
                {
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + matrix[i][j];
                }
                else if (i == 0)
                {
                    dp[i][j] = dp[i][j - 1] + matrix[i][j];
                }
                else
                {
                    dp[i][j] = dp[i - 1][j] + matrix[i][j];
                }
            }
        }

        return dp[rows - 1][cols - 1];
    }
};