题解 | #牛妹的礼物#

题意描述：
有NxM大小的矩阵，从左上角走到右下角，只能向右，下，右下走，求到达右下角的最短带权路径长度

方法一：动态规划
采用递推的方式,定义一个二维 $dp$ 数组，显然， $dp[i][j]$ 的值就是从左上角走到 $presentVolumn[i][j]$ 的最短路径，要求从左上角到右下角的最短路径就是求 $dp[m-1][n-1]$ 的值
状态转移方程：

$dp[0][1...n-1]=dp[0][j-1]+presentVolumn[i][j]$
$dp[1...m-1][0]=dp[i-1][0]+presentVolumn[i][j]$
$dp[1...n-1][1...m-1]=min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+presentVolumn[i][j]$

图片说明

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param presentVolumn int整型二维数组 N*M的矩阵，每个元素是这个地板砖上的礼物体积
     * @return int整型
     */
    public int selectPresent (int[][] presentVolumn) {
        // write code here
        int m=presentVolumn.length,n=presentVolumn[0].length;
        int[][]dp=new int[m][n];
        dp[0][0]=presentVolumn[0][0];
        int min=0;
        if(presentVolumn==null)return 0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                //第0行的元素由左边转移过来
                if(i==0&&j>=1)dp[i][j]=dp[i][j-1]+presentVolumn[i][j];
                //第0列的元素由上面的转移过来
                else if(j==0&&i>=1)dp[i][j]=dp[i-1][j]+presentVolumn[i][j];
                //非其余元素由左，上，左上的最小值转移过来
                else if(i>=1&&j>=1){
                    dp[i][j]=Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+presentVolumn[i][j];}
            }
        }
        return dp[m-1][n-1];
    }
}

空间复杂度：
时间复杂度：外层循环 $m$ 次，内层循环 $n$ 次，总的时间复杂度为 $O(mn)$
空间复杂度： $dp$ 数组的空间大小为 $m*n$ ，空间复杂度为 $O(mn)$

优化方法
在原数组上做路径的更新，降低空间复杂度
具体代码如下：

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param presentVolumn int整型二维数组 N*M的矩阵，每个元素是这个地板砖上的礼物体积
     * @return int整型
     */
    public int selectPresent (int[][] presentVolumn) {
        // write code here
        int m=presentVolumn.length,n=presentVolumn[0].length;
        if(presentVolumn==null)return 0;
        for(int j=1;j<n;j++)presentVolumn[0][j]+=presentVolumn[0][j-1];
        for(int i=1;i<m;i++){
            presentVolumn[i][0]+=presentVolumn[i-1][0];
            for(int j=1;j<n;j++){
                    presentVolumn[i][j]+=Math.min(Math.min(presentVolumn[i-1][j],presentVolumn[i][j-1]),presentVolumn[i-1][j-1]);
            }
        }
        return presentVolumn[m-1][n-1];
    }
}

空间复杂度：
时间复杂度：外层循环 $m-1$ 次，内层循环 $n-1$ 次，平均时间复杂度为 $O(mn)$
空间复杂度：原地运算，空间复杂度为 $O(1)$
方法二：记忆化搜索
递归公式为：

$i=0$ 且 $j=0$ : $f=presentVolumn[i][j]$
$i=0$ 且 $j>0$ : $f=dfs(i,j-1)+presentVolumn[i][j]$
$j=0$ 且 $i>0$ : $f=dfs(i-1,j)+presentVolumn[i][j]$
$i>0$ 且 $j>0$ : $f=min(dfs(i-1,j),dfs(i-1,j-1),dfs(i,j-1))+presentVolumn[i][j]$
为了避免重复运算，使用记忆数组保存之前已经计算过的子问题，降低递归次数
图片说明

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param presentVolumn int整型二维数组 N*M的矩阵，每个元素是这个地板砖上的礼物体积
     * @return int整型
     */
    int[][]memory;
    public int selectPresent (int[][] presentVolumn) {
        // write code here
        int m=presentVolumn.length,n=presentVolumn[0].length;
        if(presentVolumn==null)return 0;
        memory=new int[m][n];
        return dfs(m-1,n-1,presentVolumn);
    }
    int dfs(int i,int j,int[][]presentVolumn){
        //递归终止条件
        if(i==0&&j==0)return presentVolumn[0][0];
        //已经计算过的直接返回
        if(memory[i][j]!=0)return memory[i][j];
        //除了[0,0]的第一行均由本身+左边得来
        if(i==0&&j>0){
            memory[i][j]=presentVolumn[i][j]+dfs(i,j-1,presentVolumn);
            return memory[i][j];}
        //除了[0,0]的第一列均由本身+上一个得来
        else if(j==0&&i>0){
            memory[i][j]=presentVolumn[i][j]+dfs(i-1,j,presentVolumn);
            return memory[i][j];
        }
        //其他由本身+最小（上边，左上角，左边）得来
        else{
            memory[i][j]=presentVolumn[i][j]+Math.min(Math.min(dfs(i-1,j,presentVolumn),dfs(i-1,j-1,presentVolumn)),dfs(i,j-1,presentVolumn));
            return memory[i][j];
        }
    }
}

复杂度：
时间复杂度： $O(mn)$ ,递归次数不超过 $mn$ ，每次递归地时间复杂度为常数级
空间复杂度： $O(mn)$ ,递归栈和记忆数组的大小都不超过 $mn$