题解 | #牛妹的礼物#

题目描述
众所周知，牛妹有很多很多粉丝，粉丝送了很多很多礼物给牛妹，牛妹的礼物摆满了地板。
地板是N×M的格子，每个格子有且只有一个礼物，牛妹已知每个礼物的体积。
地板的坐标是左上角(1,1) 右下角（N, M）。
牛妹只想要从屋子左上角走到右下角，每次走一步，每步只能向下走一步或者向右走一步或者向右下走一步
每次走过一个格子，拿起（并且必须拿上）这个格子上的礼物。
牛妹想知道，她能走到最后拿起的所有礼物体积最小和是多少？

方法一：动态规划的方法

求解思路
对于本题目的求解，我们使用动态规划的思想进行求解，当下一步只能往右边走时，则此时数据只跟左边的数据有关。当下一步只能往下走时，则此时数据只跟上边的数据有关。根据上述思路，我们即可求得本题的答案。

图片说明

解题代码

import java.util.*;
public class Solution {
    public int selectPresent (int[][] presentVolumn) {
        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++)
            {
                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$ ( $图片说明$ )
空间复杂度：辅助数组dp[n][n],引入额外的内存地址空间，因此空间复杂度为 $O$ ( $图片说明$ )

方法二：dfs

求解思路
在基于方法一的思路上，我们通过深度优先搜索进行改进，通过深度优先搜索遍历实现向右、向下、向右下行走的过程。

图片说明

解题代码

class Solution:
    def selectPresent(self , presentVolumn ):
        h = len(presentVolumn)
        if h == 0:
            return 0
        w = len(presentVolumn[0])
        if w == 0:
            return 0
        # 初始化mydp数组
        mydp = [[-1 for i in range(w)] for j in range(h)]
        mydp[0][0] = presentVolumn[0][0]
        def dfs(i,j):
            # 最小值
            if mydp[i][j] != -1:
                return mydp[i][j]
            # 只有一列数据
            if i == 0 and j > 0:
                mydp[0][j] = dfs(0, j-1) + presentVolumn[0][j]
            # 只有一行数据
            if i > 0 and j == 0:
                mydp[i][0] = dfs(i-1, 0) + presentVolumn[i][0]
            if i > 0 and j > 0:
                # 递归方程
                mydp[i][j] = min(dfs(i-1,j), dfs(i,j-1), dfs(i-1,j-1)) + presentVolumn[i][j]
            return mydp[i][j]
        myres = dfs(h-1,w-1) # 递归
        return myres # 返回结果即可