解法一：回溯法（暴力解法）

回溯法遍历所有可走到的路线，并计算每条路线的结果，将最小的结果返回。
回溯方法通常需要两个步骤：1. 更新变量，递归到下一步；2.递归返回时，撤销更新
对于此题，在每一次递归过程中，需要将当前位置元素的路径和(代码中curSum变量)加入到结果中，并作为参数传入下一次递归；在递归完成后，需要减去数组当前位置的取值，即：撤销对curSum的更新。
由于此题允许「向右」及「向下」两种移动方式，因此需要对两个方向各进行递归。

注意递归的终止条件：1. 当前位置超出数组边界；2.已经递归到终点，即右下角位置。

注意：此递归解法的运行时间会超时。

代码如下：

int res = INT_MAX; // 定义全局变量，作为最终结果返回

class Solution {
public:
    /**
     *
     * @param matrix int整型vector<vector<>> the matrix
     * @return int整型
     */
    int row, col;
    int minPathSum(vector<vector<int> >& matrix) {
        // 此方式定义数组不需要在递归函数中作为参数传入，节省栈空间
        row = matrix.size();
        col = matrix[0].size();
        backtracking(0, 0, 0, matrix);
        return res;
    }
    void backtracking(int curRow, int curCol, int curSum, vector<vector<int> >& matrix) {
        // 递归终止条件
        if (curRow == row || curCol == col)
            return;
        // 更新当前路径和
        curSum += matrix[curRow][curCol];
        // 递归终止条件
        if (curRow == row - 1 && curCol == col - 1) {
            if (curSum < res) {
                res = curSum;
            }
            curSum -= matrix[curRow][curCol];
            return;
        }
        // 开始递归
        backtracking(curRow + 1, curCol, curSum, matrix);
        backtracking(curRow, curCol + 1, curSum, matrix);
        // 重置当前路径和
        curSum -= matrix[curRow][curCol];
    }
};

该方法对于每个元素点，分别尝试了“向右”和“向下”两种移动方式，因此总时间复杂度为指数级别，即O(2^N)；该算法未引入额外空间，因此空间复杂度为O(1)。

解法一的优化

在解法一中，递归完成进行回溯时存在重复计算，因此可以定义一个「记忆数组」，用以在回溯过程中直接利用所存储的值。

代码如下：

class Solution {
public:
    /**
     *
     * @param matrix int整型vector<vector<>> the matrix
     * @return int整型
     */
//     vector<vector<int> > mem; // mem为记忆数组
    int rows, cols;
    int minPathSum(vector<vector<int> >& matrix) {
        rows = matrix.size();
        cols = matrix[0].size();
        vector<vector<int> > mem(rows, vector<int>(cols));
        int res = backtracking(0, 0, matrix, mem); // 从左上角开始递归
        return res;
    }

    int backtracking(int row, int col, vector<vector<int> >& matrix, vector<vector<int> > &mem) {
        // 递归终止条件
        if (row >= rows || col >= cols)
            return INT_MAX;
        if (row == rows - 1 && col == rows - 1)
            return matrix[row][col];
        // 下一层递归，对应“向下”、“向右”两种方式
        int right = backtracking(row, col + 1, matrix, mem);
        int down = backtracking(row + 1, col, matrix, mem);
        // 回溯过程更新记忆数组
        mem[row][col] = min(right, down) + matrix[row][col];
        return mem[row][col];
    }
};

该方法通过构建记忆数组mem，避免如「通过不同路径总到同一位置」这类重复。因此，对于每一个(row,col)所组成的pair，只会调用递归函数一次，因此总时间复杂度为平方级别，即O(N^2)；该算法引入记忆数组，因此空间复杂度为平方级别，即O(N^2)。

注：此优化后的方法运行时间仍不能满足要求，需要尝试其他方法：动态规划。

解法二：动态规划

根据「解法一优化」方法的启发，可以想到此题最优解为动态规划方法：
动态规划方法的思想是：将原问题分解为若干子问题，称为「最优子结构」，通过求解子问题完成对最终问题的求解。对于重复出现的子问题，在第一次出现时对其进行求解，然后保存其结果，从而在求解后续的子问题时可以直接利用先前得到的结果。

针对这道题目，我们可以先思考最优子结构：题目要求得到从「左上角」到「右下角」的整个二维数组的最小路径，因此其子问题为：对于二维数组中的每个元素位置，求取从起点到该位置的最短路径；对于「右下角」的元素位置，从起点到该位置的最短路径即为最终答案。

在求解子问题时，需要构建动态转移方程，即：从「上一状态」到「下一状态」的递推式。

如下图所示，对于数组中的每一个元素[i,j]，达到该位置共有两种方式：左侧元素([i,j-1])向右移动一步，或者上方元素([i-1,j])向下移动一步。

因此，对于数组中的每个元素，从上述两种方式中选取较短的那一条路径即为到该点的最短路径。因此，可以得到求解子问题时的状态转移方程：

dp[i, j] = min(dp[i - 1][j], dp[i][j - 1]) + matrix[i][j]

在完成整个动态规划算法时，需要明确算法的推进方向，在此题中，算法的推进方向为：从左至右、从上至下，因此在进行动态规划数组数组dp的初始化时，需要分别初始化数组的「第一行」与「第一列」。

特别注意要初始化dp数组左上角元素的取值。

代码如下：

class Solution {
public:
    /**
     * 
     * @param matrix int整型vector> the matrix
     * @return int整型
     */
    int minPathSum(vector<vector<int> >& matrix) {
        int row = matrix.size(), col = matrix[0].size();
        vector<vector<int> > dp(row, vector(col)); // 定义动态规划数组dp，尺寸与输入数组一致
        dp[0][0] = matrix[0][0]; // 初始化左上角元素
        // 初始化第一行
        for (int i = 1; i < col; i ++) 
            dp[0][i] = dp[0][i - 1] + matrix[0][i]; 
        // 初始化第一列
        for (int i = 1; i < row; i ++) 
            dp[i][0] = dp[i - 1][0] + matrix[i][0]; 
        // 动态规划
        for (int i = 1; i < row; i ++) {
            for (int j = 1; j < col; j ++) {
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + matrix[i][j]; 
            }
        }
        return dp[row - 1][col - 1]; // 右下角元素结果即为答案
    }
};

该算法遍历了二维数组的每一个元素，因此时间复杂度为平方级别，即：O(N^2)；该算法定义了与原输入数组同样大小的dp数组，因此空间复杂度同样为平方级别，为O(N^2)。

解法二的优化：

对于解法二，定义了(M*N)大小的dp数组，可对其进行空间复杂度优化.

在动态规划递推过程中，其方向是「从上至下」、「从左至右」，因此可以直接对原输入数组进行修改，并不会影响后续的递推过程。
代码如下：

class Solution {
public:
    /**
     * 
     * @param matrix int整型vector<vector<>> the matrix
     * @return int整型
     */
    int minPathSum(vector<vector<int> >& matrix) {
        int row = matrix.size(), col = matrix[0].size(); 
        for (int i = 0; i < row; i ++) {
            for (int j = 0; j < col; j ++) {
                if (i == 0 && j != 0) { // 数组第一行
                    matrix[0][j] += matrix[0][j - 1];
                } else if (j == 0 && i != 0) { // 数组第一列
                    matrix[i][0] += matrix[i - 1][0]; 
                } else if (i > 0 && j > 0) {
                    // 两种方式取最小的
                    matrix[i][j] += min(matrix[i - 1][j], matrix[i][j - 1]);
                }
            }
        }
        return matrix[row - 1][col - 1];
    }
};

该算法遍历了二维数组的每一个元素，因此时间复杂度为平方级别，即：O(N^2)；该算法未采用额外空间，因此空间复杂度为O(1)。