【牛客】牛妹的礼物（动态规划）

题目链接：https://www.nowcoder.com/practice/c4f777778e3040358e1e708750bb7fb9?tpId=110&tqId=33431&tPage=1&rp=1&ru=/ta/job-code&qru=/ta/job-code/question-ranking

题目描述

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

地板是

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

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

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

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

示例1

输入

复制

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

输出

复制

说明

(1,1)->(1,2)->(2,3)

备注:

0<N,M<300

每个礼物的体积小于100

 1 class Solution {
 2 public:
 3     /**
 4      * 
 5      * @param presentVolumn int整型vector<vector<>> N*M的矩阵，每个元素是这个地板砖上的礼物体积
 6      * @return int整型
 7      */
 8     int selectPresent(vector<vector<int> >& presentVolumn) {
 9         // write code here
10         if(presentVolumn.size()==0||presentVolumn[0].size()==0) return 0;
11         int i,j,sum;
12         int n=presentVolumn.size(),m=presentVolumn[0].size();
13         int dp[n][m];
14         dp[0][0]=presentVolumn[0][0];
15         for(i=1;i<n;i++){
16             dp[i][0]=dp[i-1][0]+presentVolumn[i][0];
17         }
18         for(j=1;j<m;j++){
19             dp[0][j]=dp[0][j-1]+presentVolumn[0][j];
20         }
21         int tmp;
22         for(i=1;i<n;i++){
23             for(j=1;j<m;j++){
24                 tmp=min(dp[i-1][j-1],dp[i-1][j]);
25                 tmp=min(dp[i][j-1],tmp);
26                 dp[i][j]=tmp+presentVolumn[i][j];
27             }
28         }
29         return dp[n-1][m-1];
30     }
31 };

【牛客】牛妹的礼物 （动态规划）

题目描述

输入

输出

说明

备注:

【牛客】牛妹的礼物（动态规划）