矩阵的最小路径和

题目描述
给定一个 n * m 的矩阵 a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。

解法

  //解法：动归
    //状态定义： dp[i][j] 到（i，j）位置的最小路径和
    //状态转移：dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + num[i][j]
    //状态初始化：
    //       dp[0][0..m] = [num[0][0], dp[0][0] + num[0][1], ...]
    //       dp[0..n][m] = [num[0][0], dp[0][0] + num[1][0], ...]
    // 时间：O(n*m) 空间O（n*m)
    int minPathSum(vector<vector<int> >& matrix) {
        vector<vector<int>> dp(matrix.size(), vector<int>(matrix[0].size(), 0));
        //状态初始化
        dp[0][0] = matrix[0][0];
        for (int i = 1; i < matrix.size(); i++) {
            dp[i][0] = dp[i-1][0] + matrix[i][0];
        }
        for (int j = 1; j < matrix[0].size(); j++) {
             dp[0][j] = dp[0][j-1] + matrix[0][j];
        } 
        //状态转移
        for (int i = 1; i < matrix.size(); i++) {
            for (int j = 1; j < matrix[0].size(); ++j) {
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + matrix[i][j];
            }
        }
        return dp[matrix.size() - 1 ][matrix[0].size() - 1];
    }