我要招人

去企业版

首页 > 试题广场 >

牛妹的礼物

[编程题]牛妹的礼物

热度指数：10588 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

众所周知，牛妹有很多很多粉丝，粉丝送了很多很多礼物给牛妹，牛妹的礼物摆满了地板。

地板是 $N\times M$ 的格子，每个格子有且只有一个礼物，牛妹已知每个礼物的体积。

地板的坐标是左上角(1,1) 右下角（N, M）。

牛妹只想要从屋子左上角走到右下角，每次走一步，每步只能向下走一步或者向右走一步或者向右下走一步

每次走过一个格子，拿起（并且必须拿上）这个格子上的礼物。

牛妹想知道，她能走到最后拿起的所有礼物体积最小和是多少？

示例1

输入

[[1,2,3],[2,3,4]]

输出

说明

先走到(1,1)这个点，此时和为1，然后走到(1,2)这个点，拿起(1,2)点的数字，此时和为3，最后走到(2,3)，拿起(2,3)点的数字，此时和为7

备注:

0<N,M<300
0<=每个礼物的体积<100

算法知识视频讲解

Java

阿尼亚瓦库瓦库

动态规划轻松解题：

import java.util.*;


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

发表于 2021-05-12 14:42:39 回复(0)

Java

小龙coding

第一次做算法题学习了。

建立一个数组，里面每个位置放的对应到达这个位置要走的最短路径

1、先初始化第一排。第一列

2、其他就看他周围最小的加上它本身

发表于 2020-08-24 17:25:13 回复(0)

Java

长田语

[[1,2,3],[2,3,4]]我只想问一下这个输入用例我看不懂是什么意思

发表于 2020-08-22 12:26:08 回复(5)

Java

長情☀

编译器结果正确，在平台上却显示答案错误

import java.util.Stack;


public class Solution {
    /**
     * 
     * @param presentVolumn int整型二维数组 N*M的矩阵，每个元素是这个地板砖上的礼物体积
     * @return int整型
     */
    public int selectPresent (int[][] presentVolumn) {
        int row = 0, col = 0;
        int[][] dp = new int[presentVolumn.length][presentVolumn[0].length];
        dp[row][col] = presentVolumn[row][col];
        Stack<Integer> rowStack = new Stack<Integer>();
        rowStack.push(row);
        Stack<Integer> colStack = new Stack<Integer>();
        colStack.push(col);
        while (!rowStack.isEmpty()) {
            row = rowStack.pop();
            col = colStack.pop();
            if (row + 1 < presentVolumn.length) {
                if (dp[row + 1][col] == 0) {
                    dp[row + 1][col] = dp[row][col] + presentVolumn[row + 1][col];
                    rowStack.push(row + 1);
                    colStack.push(col);
                } else {
                    dp[row + 1][col] = Math.min(dp[row + 1][col], dp[row][col] + presentVolumn[row + 1][col]);
                }
            }
            if (col + 1 < presentVolumn[0].length) {
                if (dp[row][col + 1] == 0) {
                    dp[row][col + 1] = dp[row][col] + presentVolumn[row][col + 1];
                    rowStack.push(row);
                    colStack.push(col + 1);
                } else {
                    dp[row][col + 1] = Math.min(dp[row][col + 1], dp[row][col] + presentVolumn[row][col + 1]);
                }
            }
            if (row + 1 < presentVolumn.length && col + 1 < presentVolumn[0].length) {
                if (dp[row + 1][col + 1] == 0) {
                    dp[row + 1][col + 1] = dp[row][col] + presentVolumn[row + 1][col + 1];
                    rowStack.push(row + 1);
                    colStack.push(col + 1);
                } else {
                    dp[row + 1][col + 1] = Math.min(dp[row + 1][col + 1], dp[row][col] + presentVolumn[row + 1][col + 1]);
                }
            }
        }
        return dp[presentVolumn.length - 1][presentVolumn[0].length-1];
    }
}

发表于 2020-08-11 10:33:54 回复(0)

Java

aaacer

import java.util.*;
 
 
public class Solution {
    /**
     *
     * @param presentVolumn int整型二维数组 N*M的矩阵，每个元素是这个地板砖上的礼物体积
     * @return int整型
     */
    public int selectPresent (int[][] presentVolumn) {
        // write code here
        if (presentVolumn == null || presentVolumn.length == 0 || presentVolumn[0].length == 0)
            return 0;
 
        int N = presentVolumn.length;
        int M = presentVolumn[0].length;
 
        int[][] matrix = presentVolumn;
        for (int i = 1; i < N; i++) {
            matrix[i][0] += matrix[i - 1][0];
        }
        for (int j = 1; j < M; j++) {
            matrix[0][j] += matrix[0][j - 1];
        }
 
        for (int i = 1; i < N; i++) {
            for (int j = 1; j < M; j++) {
            matrix[i][j] += Math.min(Math.min(matrix[i - 1][j], matrix[i][j - 1]), matrix[i - 1][j - 1]);
            }
        }
        return matrix[N - 1][M - 1];
    }
}

发表于 2020-07-20 22:57:33 回复(0)

Java

我可以改名了吗

 java 应该拥有姓名
   public int selectPresent (int[][] presentVolumn) {
        // write code here
        if(presentVolumn.length == 0) {
            return 0;
        }
        int[][] ret = presentVolumn;
        //初始化第一行第一列的最优解
        if(ret[0].length > 1) {
            for (int i = 1; i < ret[0].length; i++) {
                ret[0][i] += ret[0][i - 1];
            }
        }
        if(ret.length > 1) {
            for (int i = 1; i < ret.length; i++) {
                ret[i][0] += ret[i - 1][0];
            }
        }
        if(ret.length == 1) {
            return ret[0][ret[0].length - 1];
        }
        if(ret[0].length == 1) {
            return ret[ret.length - 1][0];
        }
        for (int i = 1; i < ret.length; i++) {
            for (int j = 1; j < ret[0].length; j++) {
                ret[i][j] += Integer.min(ret[i - 1][j - 1], Integer.min(ret[i - 1][j], ret[i][j - 1]));
            }
        }
        return ret[ret.length - 1][ret[0].length - 1];
    }

发表于 2020-05-05 15:03:41 回复(0)

Java