大本赢彩票开户

码迷,xscp18.com
大本赢彩票开户 > Windows程序 > 详细

acwing 60. 礼物的最大价值

时间:2019-08-31 01:19:20      阅读:92      评论:0      收藏:0      [点我收藏+]

标签:==   大于   nbsp   XML   turn   pre   ram   i++   rev   

地址 

在一个m×n的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于0)。

你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格直到到达棋盘的右下角。

给定一个棋盘及其上面的礼物,请计算你最多能拿到多少价值的礼物?

注意:

  • m,n>0m,n>0

样例:

输入:
[
  [2,3,1],
  [1,7,1],
  [4,6,1]
]

输出:19

解释:沿着路径 23761 可以得到拿到最大价值礼物。

解法

动态规划 由于只能在格子上 向右或者向下走 那么可以得到状态转移方程

dp[i][j] = dp[i][j] + max(dp[i-1][j] , dp[i][j-1]);

class Solution {
public:
    int getMaxValue(vector<vector<int>>& grid) {
        if(grid.size() == 0 || grid[0].size() == 0) return 0;
        
        int n = grid.size(); int m = grid[0]。size();    
        vector<vector<int>> dp(n+10,vector<int>(m+10,0));
        
        dp[0][0] = grid[0][0];
        for(int i =0;i < n;i++){
            for(int j = 0;j <m;j++){
                dp[i][j] = grid[i][j];
            }
        }
        
        for(int i = 0 ;i < n ;i++){
            for(int j = 0;j < m;j++){
                int up = 0;int left = 0;
                if(i-1 >= 0) up = dp[i-1][j];
                if(j-1 >=0) left = dp[i][j-1];
                dp[i][j] += max(up,left);
            }
        }
        
        return dp[n-1][m-1];
        
    }
};

 

acwing 60. 礼物的最大价值

标签:==   大于   nbsp   XML   turn   pre   ram   i++   rev   

原文地址:https://www.cnblogs.com/itdef/p/11437596.html

(0)
(0)
   
举报
评论 一句话评论(0
登录后才能评论!
           
© 2014 xscp18.com 版权所有 京ICP备13008772号-2
迷上了代码!
胜通彩票开户 第1彩票开户 纵达彩票开户 彩世界开户 5360彩票开户 鼎盛彩票开户 红韵彩票开户 旺旺彩票开户 乐米彩票开户 全民彩票注册