题解 | #礼物的最大价值#

礼物的最大价值

http://www.nowcoder.com/practice/2237b401eb9347d282310fc1c3adb134

这个题虽然是 中等的动态规划题,确实简单。简单在于状态转移方程只有四种情况。
默认当前位置的价值为当前礼品的价值。
1.如果当前位置行列数都大于0,当前位置的价值需加上左边位置跟上边位置的最大值
2.如果当前位置只有行数大于0,当前位置的价值需加上上边位置的值
3.如果当前位置只有列数大于0,当前位置的价值需加上左边位置的值
4.当前位置在左上角,价值不变。
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param grid int整型vector<vector<>> 
     * @return int整型
     */
    int maxValue(vector<vector<int> >& grid) {
        // write code here
        int m = grid.size();
        if(m == 0){
            return 0;
        }
        int n = grid[0].size();
        vector<vector<int> >dp = vector<vector<int> > (m,vector<int>(n,0));
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                dp[i][j] = grid[i][j];
                if(i > 0 && j > 0){
                    dp[i][j] += max(dp[i][j-1],dp[i-1][j]);
                }else if(i>0){
                    dp[i][j] += dp[i-1][j];
                }else if(j>0){
                    dp[i][j] += dp[i][j-1];
                }
            }
        }
        return dp[m-1][n-1];
    }
};


全部评论

相关推荐

当初高考报计算机真是造大孽了啊!卷的飞起!哪都是计算机的人,考研,考公,找工作全他奶的计算机的人,太难了。国企也是。关键一届比一届卷,造大孽了!
_Lyrics_:因为计算机,没有体验到快乐的大学研究生时光,好不容易修完课程就要出去实习,看着别人专业可以一起搓麻将,游山玩水,而我却要自己一个人住在北上不到十平米的出租屋,每天两点一线
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务