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

#include <cstdlib>
#include <iterator>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param matrix int整型vector<vector<>> the matrix
     * @return int整型
     */
    int minPathSum(vector<vector<int> >& matrix) {
        // write code here
        int n = matrix.size();
        int m = matrix[0].size();
     vector<vector<int>> x(n, vector<int>(n));
        // x[0] = matr;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if(i==0&&j==0){
                    x[i][j]=matrix[i][j];
                }

                else if (i == 0&&j!=0) {
                    x[i][j] = matrix[i][j] + x[i][j - 1];
                }
                else if (i!=0&&j == 0) {
                    x[i][j] = matrix[i][j] + x[i-1][j];
                }
                else {
                    x[i][j] = matrix[i][j] + min(x[i - 1][j], x[i][j-1]);
                }

            }
        }
        return x[n - 1][m - 1];
    }
};

只能向下或者向后 。 那么当前位置最短路径x【i,j】就是左一个位置或者上一个位置过来，选这两个位置上的最短路径加上matrix[i][j]。需要注意，当在边时，只有一种操作，需要注意，最短路径就是沿着另一方向的前一个位置的最短路径加上当前位置的值。当到起点时，那无路走，就是matrix[0][0];返回这样构建后的x的终点位置的值。