题目链接:https://www.nowcoder.com/practice/c4f777778e3040358e1e708750bb7fb9?tpId=110&tqId=33431&tPage=1&rp=1&ru=/ta/job-code&qru=/ta/job-code/question-ranking
题目描述
众所周知,牛妹有很多很多粉丝,粉丝送了很多很多礼物给牛妹,牛妹的礼物摆满了地板。
地板是
N\times MN×M的格子,每个格子有且只有一个礼物,牛妹已知每个礼物的体积。
地板的坐标是左上角(1,1) 右下角(N, M)。
牛妹只想要从屋子左上角走到右下角,每次走一步,每步只能向下走一步或者向右走一步或者向右下走一步
每次走过一个格子,拿起(并且必须拿上)这个格子上的礼物。
牛妹想知道,她能走到最后拿起的所有礼物体积最小和是多少?
示例1
输入
复制
[[1,2,3],[2,3,4]]
输出
复制
7
说明
(1,1)->(1,2)->(2,3)
备注:
0
1 class Solution {
2 public:
3 /**
4 *
5 * @param presentVolumn int整型vector> N*M的矩阵,每个元素是这个地板砖上的礼物体积
6 * @return int整型
7 */
8 int selectPresent(vectorint> >& 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){
16 dp[i][0]=dp[i-1][0]+presentVolumn[i][0];
17 }
18 for(j=1;j){
19 dp[0][j]=dp[0][j-1]+presentVolumn[0][j];
20 }
21 int tmp;
22 for(i=1;i){
23 for(j=1;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 };