本文共 953 字，大约阅读时间需要 3 分钟。

题目

在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

思路

直接动态规划了，主要是要写出状态转移方程

代码

class Solution {public:    int max(int a,int b){        if(a > b){            return a;        }else{            return b;        }    }    int maxValue(vector
   
    
     >& grid) {        int m = grid.size();        if(m <= 0){            return 0;        }        int n = grid[0].size();        for(int i = 0;i < m;i++){            for(int j = 0;j < n;j++){                if(i == 0 && j == 0){                    grid[i][j] = grid[i][j];                }else if(i == 0){                    grid[i][j] = grid[i][j-1] + grid[i][j];                }else if(j == 0){                    grid[i][j] = grid[i-1][j] + grid[i][j];                }else{                    grid[i][j] = max(grid[i-1][j],grid[i][j-1]) + grid[i][j];                }            }        }        return grid[m-1][n-1];    }};
    
   

转载地址：https://blog.csdn.net/hanmin822/article/details/105876024 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！