众所周知，牛妹有很多很多粉丝，粉丝送了很多很多礼物给牛妹，牛妹的礼物摆满了地板。
地板是
的格子，每个格子有且只有一个礼物，牛妹已知每个礼物的体积。
地板的坐标是左上角(1,1) 右下角（N, M）。
牛妹只想要从屋子左上角走到右下角，每次走一步，每步只能向下走一步或者向右走一步或者向右下走一步
每次走过一个格子，拿起（并且必须拿上）这个格子上的礼物。
牛妹想知道，她能走到最后拿起的所有礼物体积最小和是多少？
[编程题]牛妹的礼物
class Solution {
public:
/**
*
* @param presentVolumn int整型vector<vector<>> N*M的矩阵，每个元素是这个地板砖上的礼物体积
* @return int整型
*/
int selectPresent(vector<vector<int> >& presentVolumn) {
int n=presentVolumn.size(), m=presentVolumn[0].size();
if(n==0 || m==0)
return 0;
for(int i=1;i<m;i++)
presentVolumn[0][i] += presentVolumn[0][i-1];
for(int i=1;i<n;i++)
presentVolumn[i][0] += presentVolumn[i-1][0];
for(int i=1;i<n;i++)
for(int j=1;j<m;j++)
presentVolumn[i][j] += min(presentVolumn[i-1][j-1], min(presentVolumn[i-1][j], presentVolumn[i][j-1]));
return presentVolumn[n-1][m-1];
}
};
发表于 2020-07-08 09:31:14
回复(0)
class Solution {
public:
/**
*
* @param presentVolumn int整型vector<vector<>> N*M的矩阵，每个元素是这个地板砖上的礼物体积
* @return int整型
*/
int selectPresent(vector<vector<int> >& presentVolumn) {
// write code here
if(presentVolumn.size()==0||presentVolumn[0].size()==0) return 0;
int i,j,sum;
int n=presentVolumn.size(),m=presentVolumn[0].size();
int dp[n][m];
dp[0][0]=presentVolumn[0][0];
for(i=1;i<n;i++){
dp[i][0]=dp[i-1][0]+presentVolumn[i][0];
}
for(j=1;j<m;j++){
dp[0][j]=dp[0][j-1]+presentVolumn[0][j];
}
int tmp;
for(i=1;i<n;i++){
for(j=1;j<m;j++){
tmp=min(dp[i-1][j-1],dp[i-1][j]);
tmp=min(dp[i][j-1],tmp);
dp[i][j]=tmp+presentVolumn[i][j];
}
}
return dp[n-1][m-1];
}
};
发表于 2020-04-09 23:48:30
回复(0)
题目说了n > 0还给n==0的测试样例 恶意满满。注意还可以向右下走，比一般的题目多一条路
int selectPresent(vector<vector<int> >& pv) {
int n = pv.size(); if(n == 0) return 0;
int m = pv[0].size();
for(int i = 1; i < n; i++) pv[i][0] += pv[i-1][0];
for(int i = 1; i < m; i++) pv[0][i] += pv[0][i-1];
for(int i = 1; i < n; i++)
for(int j = 1; j < m; j++)
pv[i][j] += min(pv[i][j-1], min(pv[i-1][j], pv[i-1][j-1]));
return pv[n-1][m-1];
}
发表于 2020-05-12 12:13:22
回复(0)
动态规划轻松解题：
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)
个人感觉我的这个是使用递归的方法做的，个人感觉是没错的，就是复杂度太大了，运行时间超时！
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;
int M=presentVolumn[0].length;
return Cost(N-1,M-1,presentVolumn);
}
public int Cost(int N,int M,int[][] presentVolumn){
int key,a,b,c;
if(N>0&&M>0){
a=Cost(N-1,M,presentVolumn);
b=Cost(N,M-1,presentVolumn);
c=Cost(N-1,M-1,presentVolumn);
key=Math.min(Math.min(a,b),c)+presentVolumn[N][M];
}
else if(N==0&&M>0){
key=Cost(N,M-1,presentVolumn)+presentVolumn[N][M];
}
else if(N>0&&M==0){
key=Cost(N-1,M,presentVolumn)+presentVolumn[N][M];
}else{
key=presentVolumn[N][M];
}
return key;
}
}
发表于 2020-10-11 22:49:51
回复(0)
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 rowCount = presentVolumn.length;
int colomCount = presentVolumn[0].length;
int[][] dp = new int[rowCount][colomCount];
for (int i = 0;i<rowCount;i++){
for (int j =0; j<colomCount;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[rowCount-1][colomCount-1];
}
}
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 rowCount = presentVolumn.length;
int colomCount = presentVolumn[0].length;
int[][] dp = new int[rowCount][colomCount];
for (int i = 0;i<rowCount;i++){
for (int j =0; j<colomCount;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[rowCount-1][colomCount-1];
}
}
发表于 2020-09-06 13:19:59
回复(0)
class Solution: def selectPresent(self , presentVolumn ): # write code here rows = len(presentVolumn) cols = len(presentVolumn[0]) if rows == 0&nbs***bsp;cols == 0: return 0 dp = [[0]*cols for i in range(rows)] dp[0] = presentVolumn[0].copy() for i in range(1, rows): dp[i][0] = presentVolumn[i][0] for i in range(1, cols): dp[0][i] += dp[0][i-1] for i in range(1, rows): dp[i][0] += dp[i-1][0] for i in range(1, rows): for j in range(1, cols): dp[i][j] = min(( dp[i-1][j-1], dp[i-1][j], dp[i][j-1] )) + presentVolumn[i][j] return dp[i][j]入门级DP题
发表于 2020-08-22 07:09:10
回复(0)
class Solution: def selectPresent(self , presentVolumn ): # write code here if not presentVolumn: return 0 m = len(presentVolumn) n = len(presentVolumn[0]) dp = presentVolumn for i in range(1,m): dp[i][0]+=dp[i-1][0] for j in range(1,n): dp[0][j]+=dp[0][j-1] for i in range(1,m): for j in range(1,n): dp[i][j]+=min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1]) return dp[m-1][n-1]动态规划的题，不过python通过的空间好高啊。。。
发表于 2020-08-21 14:44:52
回复(0)
//动态规划，左边，左上，上边元素最优的最优（最小值）加上元素本身是为最优。
public int selectPresent (int[][] presentVolumn) {
int n = presentVolumn.length;
int m = presentVolumn[0].length;
int[][] dp = new int[n+1][m+1];
for(int i = 0;i<=n ;i++){
dp[i][0] = Integer.MAX_VALUE;
}
for(int i = 0;i<=m ;i++){
dp[0][i] = Integer.MAX_VALUE;
}
dp[1][1] = presentVolumn[0][0];
for(int i=0;i<n;i++){
int j=0;
if(i==0){
j=1;
}
for(;j<m;j++){
dp[i+1][j+1] = Math.min(dp[i][j],Math.min(dp[i+1][j],dp[i][j+1])) + presentVolumn[i][j];
}
}
return dp[n][m];
}
编辑于 2020-08-19 01:12:40
回复(0)
编译器结果正确，在平台上却显示答案错误
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)
import java.util.*;
public class Solution {
/**
*
* @param presentVolumn int整型二维数组 N*M的矩阵，每个元素是这个地板砖上的礼物体积
* @return int整型
*/
public int selectPresent (int[][] presentVolumn) {
if(presentVolumn == null || presentVolumn.length == 0){
return 0;
}
int n = presentVolumn.length;
int m = presentVolumn[0].length;
int[][] dp = new int[n+1][m+1];
for(int i=1;i<=n;i++){
dp[i][1] = presentVolumn[i-1][0] + dp[i-1][1];
}
for(int i=1;i<=m;i++){
dp[1][i] = presentVolumn[0][i-1] + dp[1][i-1];
}
for(int i=2;i<=n;i++){
for(int j=2;j<=m;j++){
dp[i][j] = presentVolumn[i-1][j-1] + Math.min(Math.min(dp[i-1][j], dp[i][j-1]), dp[i-1][j-1]);
}
}
return dp[n][m];
}
}
发表于 2020-08-10 18:56:01
回复(0)
public class Solution {
/**
*
* @param presentVolumn int整型二维数组 N*M的矩阵，每个元素是这个地板砖上的礼物体积
* @return int整型
*/
public int selectPresent (int[][] presentVolumn) {
// 数组大小为0时返回0
if (presentVolumn.length == 0 || presentVolumn[0].length == 0){
return 0;
}
int n = presentVolumn.length;
int m = presentVolumn[0].length;
// 初始化数组
int dp[][] = presentVolumn;
// 初始化第一行
for (int i = 1; i < n; i++){
dp[i][0] += dp[i - 1][0];
}
// 初始化第一列
for (int j = 1; j < m; j++){
dp[0][j] += dp[0][j - 1];
}
// 当前位置最小值为（左上，上，左中最小值加上当前值）
for (int i = 1; i < n; i++){
for (int j = 1; j < m; j++){
dp[i][j] += Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]);
}
}
return dp[n- 1][m - 1];
}
}
发表于 2020-08-10 16:53:18
回复(0)
class Solution:
def selectPresent(self , presentVolumn ):
# write code here
# 首先考虑数组为空的情况
if not presentVolumn: return 0
# 计算出数组的维度
N, M = len(presentVolumn),len(presentVolumn[0])
# 初始化dp数组
dp = [[float("inf") for i in range(M+1)] for j in range(N+1)]
dp[0][0] = 0
for i in range(1,N+1):
dp[i][0] = dp[i-1][0] + presentVolumn[i-1][0]
for j in range(1,M+1):
dp[0][j] = dp[0][j-1] + presentVolumn[0][j-1]
for i in range(1,N+1):
for j in range(1,M+1):
# 状态转移方程
dp[i][j] = presentVolumn[i-1][j-1] + min(dp[i-1][j],dp[i-1][j-1],dp[i][j-1])
return dp[N][M]
发表于 2020-08-07 19:59:47
回复(0)
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)
最重要的是用一个和输入同形的矩阵记录达到每一个位置的最小体积和，从行列小的到行列大的记录。
class Solution: def selectPresent(self , presentVolumn ): if not presentVolumn: return 0 N = len(presentVolumn) M = len(presentVolumn[0]) pd = [[0 for col in range(M)] for row in range(N)] # 用来记录到达每一位置最少的体积和 pd[0][0] = presentVolumn[0][0] for i in range(1, N): # 记录第一列每个位置的最小体积和 pd[i][0] = pd[i - 1][0] + presentVolumn[i][0] for j in range(1, M): # 记录第一行每个位置的最小体积和 pd[0][j] = pd[0][j - 1] + presentVolumn[0][j] for i in range(1, N): # 记录其他所有位置的最小体积和 for j in range(1, M): pd[i][j] = min(pd[i - 1][j], pd[i][j - 1], pd[i - 1][j - 1]) + presentVolumn[i][j] return pd[N - 1][M - 1]
发表于 2020-06-02 00:38:45
回复(0)
问题信息
难度：
30条回答
26收藏
6432浏览
通过挑战的用户
查看代码-
2022-06-26 17:21:10 -
2022-05-19 11:02:45
-
2022-05-02 22:58:37 -
2022-03-28 09:42:33 -
2022-03-16 22:52:52
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
