题解 | #牛妹的礼物#

思路：

题目的主要信息：

矩阵不为空，且矩阵中的内容非负数
总体上要从矩阵的左上角到右下角，每次可以选择向下、向右、向右下三个方向
路过矩阵每个格子中的数累加，求最短路径和

事实上，这道题就是一个求矩阵最短路径和的问题，只不过它是有三个方向可以选择。

方法一：递归（超时）
具体做法：
容易想到的是，在第一步时可以选择向右、向下或者右下，只需要当前的路径值加上 $(n,m-1)$ 、 $(n-1,m)$ 或 $(n-1,m-1)$ 的矩阵路径即可，加上谁，自然是其中较小者。而 $(n,m-1)$ 、 $(n-1,m)$ 和 $(n-1,m-1)$ 又是 $(n,m)$ 的子问题，可以继续递归下去。只需要用i，j表示当前位置，后续限制边界的向下或者向右即可。这是容易想到的方法，缺点是重复计算太多，会超时。
图片说明

class Solution {
public:
    int minPath(vector<vector<int> >& matrix, int i, int j){
        int n = matrix.size();
        int m = matrix[0].size();  //因为n,m均大于等于1
        //当i的值为n-1且j的值为m-1时,走到了右下角
        if(i == n - 1 && j == m - 1)
            return matrix[i][j]; //直接返回右下角的数值
        //当i的值为n- 1且j的值不为m- 1时，只能往右走
        if(i == n - 1 && j != m - 1)
            return matrix[i][j] + minPath(matrix, i ,j + 1);
        else if(i != n - 1 && j == m - 1)  //反之，只能往下走
            return matrix[i][j] + minPath(matrix, i + 1, j);
        //其他情况都可以走，选择子问题中最短的加上此时的数字即可
        int a =  minPath(matrix, i, j + 1);
        int b =  minPath(matrix, i + 1, j);
        int c =  minPath(matrix, i + 1, j + 1); //找到三种选择中的最小值
        int temp = min(a, b);
        temp = min(temp, c);
        return matrix[i][j] + temp;
    }
    int selectPresent(vector<vector<int> >& presentVolumn) {
        return minPath(presentVolumn, 0, 0);
    }
};

复杂度分析：

时间复杂度： $O(3^n)$ ，三种选择的树型递归
空间复杂度： $O(n)$ ，递归栈的最大深度

方法二：递归改进（空间记忆搜索）
具体做法：
因为递归是优先计算低级子问题，由此重复计算了很多子问题，导致超时，因此可以用一个dp二位数组来记录曾经算过的值，递归过程用到时直接用数组的值而不需要重新进行子递归。
图片说明

class Solution {
public:
    int minPath(vector<vector<int> >& matrix, int i, int j, vector<vector<int>>& dp){
        int n = matrix.size();
        int m = matrix[0].size();  //因为n,m均大于等于1
        //当i的值为n-1且j的值为m-1时,走到了右下角
        if(i == n - 1 && j == m - 1)
            return dp[i][j] = matrix[i][j];  //直接返回右下角的数值
        //当i的值为n- 1且j的值不为m- 1时，只能往右走
        if(i == n - 1 && j != m - 1){
            if(dp[i][j + 1] != -1){    //若是之前计算过这部分就不需要重复计算，直接用
                return matrix[i][j] + dp[i][j + 1];
            }
            else{
                dp[i][j + 1] = minPath(matrix, i ,j + 1, dp);  //若是没有，则计算后储存
                return matrix[i][j] + dp[i][j + 1];
            }
        }
        else if(i != n - 1 && j == m - 1)  //反之，只能往下走
            if(dp[i + 1][j] != -1){
                return matrix[i][j] + dp[i + 1][j];
            }
            else{
                dp[i + 1][j] = minPath(matrix, i + 1 ,j, dp);
                return matrix[i][j] + dp[i + 1][j];
            }
        //其他情况都可以走，选择子问题中最短的加上此时的数字即可,利用好dp数组中存储的计算过的信息
        int a = 0, b = 0, c = 0; //三种情况
        if(dp[i][j + 1] != -1) 
            a = dp[i][j + 1];
        else{
            dp[i][j + 1] = minPath(matrix, i, j + 1, dp);
            a = dp[i][j + 1];
        }
        if(dp[i + 1][j] != -1)
            b = dp[i + 1][j];
        else{
            dp[i + 1][j] = minPath(matrix, i + 1, j, dp);
            b = dp[i + 1][j];
        }
        if(dp[i + 1][j + 1] != -1)
            c = dp[i + 1][j + 1];
        else{
            dp[i + 1][j + 1] = minPath(matrix, i + 1, j + 1, dp);
            c = dp[i + 1][j + 1];
        }
        int temp = min(a, b);
        temp = min(temp, c);    //三种情况的最小值
        return matrix[i][j] + temp;
    }
    int selectPresent(vector<vector<int> >& presentVolumn) {
        int n = presentVolumn.size();
        int m = presentVolumn[0].size();
        vector<vector<int> > dp(n + 1, vector<int>(m + 1, -1));
        return minPath(presentVolumn, 0, 0, dp);
    }
};

复杂度分析：

时间复杂度： $O(nm)$ ，遍历了整个二维数组dp，其边长就是给定矩阵的边长
空间复杂度： $O(nm)$ ，dp二维数组的构建

方法三：动态规划
具体做法：

设置 $dp[i][j]$ 表示当前 $(i,j)$ 位置时的最短路径；
确立公式，当前的最短路径为 $dp[i][j]$ ，则上一步要么是 $(i,j-1)$ 往右，要么是 $(i-1,j)$ 往下，要么是 $(i-1,j-1)$ 往右下，则取其中较小的值即可得到当前公式： $dp[i][j] = min(dp[i-1][j], dp[i][j-1],dp[i-1][j-1]) + matrix[i][j]$ ；
确立边界，第一行： $dp[0][j] = dp[0][j-1]+ matrix[0][j]$ ，第一列： $dp[i][0] = dp[i-1][0]+ matrix[i][0]$ ，因为要在第一行必须是往右移动，要在第一列必须是往下移动；
最后 $dp[n-1][m-1]$ 即为所求的最短路径。

class Solution {
public:
    int selectPresent(vector<vector<int> >& presentVolumn) {
        int n = presentVolumn.size();
        int m = presentVolumn[0].size();
        vector<vector<int> > dp(n + 1, vector<int>(m + 1, 0));
        dp[0][0] = presentVolumn[0][0];//dp[i][j]表示以当前i，j位置为终点的最短路径长度
        for(int i = 1; i < n; i++)//处理第一列
             dp[i][0] = presentVolumn[i][0] + dp[i-1][0];
        for(int j = 1; j < m; j++)//处理第一行
             dp[0][j] = presentVolumn[0][j] + dp[0][j-1];
        for(int i = 1; i < n; i++){ //其他按照公式来
            for(int j = 1; j < m; j++){
                int temp = min(dp[i - 1][j], dp[i][j - 1]); //三者较小值
                temp = min(temp, dp[i - 1][j - 1]);
                dp[i][j] = presentVolumn[i][j] + temp;
            }
        }
        return dp[n-1][m-1];
    }
};

复杂度分析：

时间复杂度： $O(nm)$ ，遍历了整个二维数组dp，其边长就是给定矩阵的边长
空间复杂度： $O(nm)$ ，辅助矩阵dp