题解 | #牛妹的礼物#

算法思想一：动态规划

解题思路：

简单的动态规划，直接走就行了，
1、当只有一行的数据只能右边走所以数据只跟左边的数据有关
2、当只有一列的数据只能从上面往下走，只跟上面数据有关
3、其他情况可以来自三个方向，上面，下面，左上来计算

算法流程：

1、两层遍历矩阵 row属于【0，N】，col 属于【0，M】

1、第一行的只能左边来，动态方程： $presentVolumn[row][col]+=presentVolumn[row][col-1]$

2、第一列只能上面来，动态方程： $presentVolumn[row][col]+=presentVolumn[row-1][col]$

3、其他方式有两种从左上，动态方程： $presentVolumn[row][col]+=Math.min(Math.min(presentVolumn[row-1][col],presentVolumn[row][col-1]),presentVolumn[row-1][col-1])$

2、最后返回 $presentVolumn[N-1][M-1]$

图解：

代码展示：

JAVA版本

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param presentVolumn int整型二维数组 N*M的矩阵，每个元素是这个地板砖上的礼物体积
     * @return int整型
     */
    public int selectPresent (int[][] presentVolumn) {
        // write code here
        // 初始化
        int N=presentVolumn.length;
        if(N==0) return 0;
        int M=presentVolumn[0].length;
        // 双层循环
        for(int row=0;row<N;row++){
            for (int col=0;col<M;col++){
                //Default state
                if(row==0&&col==0) continue;
                //第一行的只能左边来
                if(row==0)
                    presentVolumn[row][col]+=presentVolumn[row][col-1];
                //第一列只能上面来
                if(col==0)
                    presentVolumn[row][col]+=presentVolumn[row-1][col];
                //其他方式有两种 从左上
                if(col!=0&&row!=0){
                    presentVolumn[row][col]+=Math.min(Math.min(presentVolumn[row-1][col],presentVolumn[row][col-1]),presentVolumn[row-1][col-1]);
                }
            }
        }
        return presentVolumn[N-1][M-1];
    }
}

复杂度分析

时间复杂度 $O(NM)$ ：N M表示二维矩阵的大小，双层遍历时间

空间复杂度 $O(1)$ ：未使用额外空间

算法思想二：动态规划+dfs

解题思路：

此方法和方法一有同样的解题思路，不同点在于方法一主要采用双层遍历进行动态方程的更新计算，方法二是通过深度优先遍历递归进行动态方程计算

主要是通过深度优先遍历dfs实现向右、向下、右下行走过程

代码展示：

Python版本

class Solution:
    def selectPresent(self , presentVolumn ):
        # write code here
        h = len(presentVolumn)
        if h == 0:
            return 0
        w = len(presentVolumn[0])
        if w == 0:
            return 0
        # 初始化dp数组
        dp = [[-1 for i in range(w)] for j in range(h)]
        dp[0][0] = presentVolumn[0][0]
        def dfs(i,j):
            # 最小值
            if dp[i][j] != -1:
                return dp[i][j]
            # 只有一列数据
            if i == 0 and j > 0:
                dp[0][j] = dfs(0, j-1) + presentVolumn[0][j]
            # 只有一行数据
            if i > 0 and j == 0:
                dp[i][0] = dfs(i-1, 0) + presentVolumn[i][0]
            if i > 0 and j > 0:
                # 递归方程
                dp[i][j] = min(dfs(i-1,j), dfs(i,j-1), dfs(i-1,j-1)) + presentVolumn[i][j]
            return dp[i][j]
        # 递归
        res = dfs(h-1,w-1)
        return res

复杂度分析

时间复杂度 $O(NM)$ ：N M表示二维矩阵的大小，深度递归时间

空间复杂度 $O(NM)$ ：dp数组占用空间