题解 | #牛妹的礼物#

题目：牛妹的礼物
描述：众所周知，牛妹有很多很多粉丝，粉丝送了很多很多礼物给牛妹，牛妹的礼物摆满了地板。地板是N×M的格子，每个格子有且只有一个礼物，牛妹已知每个礼物的体积。
地板的坐标是左上角(1,1) 右下角（N, M）。
牛妹只想要从屋子左上角走到右下角，每次走一步，每步只能向下走一步或者向右走一步或者向右下走一步
每次走过一个格子，拿起（并且必须拿上）这个格子上的礼物。
牛妹想知道，她能走到最后拿起的所有礼物体积最小和是多少？
示例1：输入：[[1,2,3],[2,3,4]]，返回值：7
说明：先走到(1,1)这个点，此时和为1，然后走到(1,2)这个点，拿起(1,2)点的数字，此时和为3，最后走到(2,3)，拿起(2,3)点的数字，此时和为7

解法一：
思路分析：首先我们分析题目，题目的意思是给定一个二维数组的具体值，然后通过从presentVolumn[0][0]开始走，每次只能向下走或者向右走或者向右下一步，以此来计算走到最后拿起的所有礼物的体积最小和是多少。
——通过这个思想我们可以设定一个都是0的二维数组dp，二维数组dp的长度和该presentVolumn数组的长度值相同，用来记录所走步数的总和，因为每走一步只有三种可能性，向下，向右，或者向右下，所以我们可以通过dp数组来记录所需要走的最小步数总和，因此，我们需要设置两个指针i和j，需要三个for循环进行分别判断。
实例分析：[[1,2,3],[2,3,4]]

Python核心代码为：

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param presentVolumn int整型二维数组 N*M的矩阵，每个元素是这个地板砖上的礼物体积
# @return int整型
#
class Solution:
    def selectPresent(self , presentVolumn ):
        # write code here
        nlen = len(presentVolumn)##行
        mlen = len(presentVolumn[0])##列

        dp = [[0 for j in range(mlen)] for i in range(nlen)]#创造数组
        dp[0][0] = presentVolumn[0][0]#初始值赋值给dp数组
        for i in range(1,nlen):#向下走
            dp[i][0] = dp[i - 1][0] + presentVolumn[i][0]
        for j in range(1,mlen):#向右走
            dp[0][j] = dp[0][j - 1] + presentVolumn[0][j]
        for i in range(1,nlen):#斜着走
            for j in range(1,mlen):
                dp[i][j] = presentVolumn[i][j] + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])#三个方向的最小值
        sum1 = dp[nlen - 1][mlen - 1]#返回
        return sum1

Java核心代码：

import java.util.*;
public class Solution {
    /**
     * 
     * @param presentVolumn int整型二维数组 N*M的矩阵，每个元素是这个地板砖上的礼物体积
     * @return int整型
     */
    public int selectPresent (int[][] presentVolumn) {
        // write code here
        List<Integer> list = new ArrayList<Integer>();//用来存放比较对象
        int nlen = presentVolumn.length;
        int mlen = presentVolumn[0].length;
        int[][] dp = new int[nlen][mlen];//创建数组
        for (int i = 0;i < nlen;i++){
            for (int j = 0; j < mlen;j++){
                if (i == 0 && j == 0){//初始化第一个的值
                    dp[i][j] = presentVolumn[0][0];
                }
                else if (i == 0 && j != 0){
                    dp[i][j] = dp[i][j - 1] + presentVolumn[i][j];
                }
                else if (j == 0 && i != 0){
                    dp[i][j] = dp[i - 1][j] + presentVolumn[i][j];
                }
                else{
                    int sum1 = dp[i][j - 1] + presentVolumn[i][j];
                    int sum2 = dp[i - 1][j] + presentVolumn[i][j];
                    int sum3 = dp[i - 1][j-1] + presentVolumn[i][j];
                    list.add(sum1);//添加
                    list.add(sum2);
                    list.add(sum3);
                    Collections.sort(list);//排序
                    dp[i][j] = list.get(0);//获得最小值
                    list.clear();//清空
                }
            }
        }
        return dp[nlen - 1][mlen - 1];
    }
}

——因为在上述代码中，采用三个for循环，最后一个for循环的时间最长，假设行执行N，列执行M，所以时间复杂度为，因为构建了一个二维的存储空间dp，所以空间复杂度为。

解法二：
思路分析：因为已知了三种行走的方向，所以上述代码我们也可以通过三个min函数进行判断，也就是右和下判断一次，再将两个的最小值和右下判断一次，最后再与数组的当前值判断一次，最后输出即可。
C++核心代码为：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param presentVolumn int整型vector<vector<>> N*M的矩阵，每个元素是这个地板砖上的礼物体积
     * @return int整型
     */
    int selectPresent(vector<vector<int> >& presentVolumn) {
        // write code here
        int nlen = presentVolumn.size();//行
        if(nlen == 0) 
            return 0;
        int mlen = presentVolumn[0].size();//列
        if(mlen == 0) 
            return 0;
        int dp[nlen + 1][mlen + 1];
        memset(dp,0x3f,sizeof(dp));//重新设置dp数组的值
        dp[0][0] = 0;//初始值设定
        for(int i = 1;i <= nlen;++i){
            for(int j = 1;j <= mlen;++j){
                int val = min(dp[i][j - 1],dp[i - 1][j]);//右与下的最小值
                val = min(val,dp[i - 1][j - 1]);//与右下的比较
                dp[i][j] = min(dp[i][j],presentVolumn[i - 1][j - 1] + val);//返回
            }
        }
        return dp[nlen][mlen];
    }
};

——因为还是需要将行与列循环一次，所以其时间复杂度为，同样设置了一个dp的二维数组，所以其空间复杂度为。