礼物的最大价值
描述
在一个m×n的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
如输入这样的一个二维数组， [ [1,3,1], [1,5,1], [4,2,1] ]
那么路径 1→3→5→2→1 可以拿到最多价值的礼物，价值为12
示例1
输入：
[[1,3,1],[1,5,1],[4,2,1]]
返回值：
12
备注：
0 < grid.length <= 2000 < grid[0].length <= 200
思路/解法
方式一
使用动态规划算法，建立二维数组dp用于保存当前位置的最大价值。其状态转移方程为dp[i][j] = dp[i-1][j] > dp[i][j-1]?dp[i-1][j]+grid[i][j]:dp[i][j-1]+grid[i][j];表示第i行第j列位置的最大价值等于左边和上方的最大值加上当前位置的价值之和。
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param grid int整型vector
* @return int整型
*/
int maxValue(vector
vector
//dp数组初始化，第一行和第一列，由于第一行和第一列不需要进行比较，仅仅等于当前位置前面的数累加和。
dp[0][0] = grid[0][0];
for(int i = 1;i dp[0][i] = dp[0][i-1] + grid[0][i]; for(int j = 1;j dp[j][0] = dp[j-1][0] + grid[j][0]; for(int i = 1;i < grid.size();i++) for(int j =1;j < grid[0].size();j++) dp[i][j] = dp[i-1][j] > dp[i][j-1]?dp[i-1][j]+grid[i][j]:dp[i][j-1]+grid[i][j]; return dp[grid.size()-1][grid[0].size()-1]; } }; 优化算法： int maxValue(vector int dp[1000][1000]{0}; dp[1][1]=g[0][0]; int n=g.size(); int m=g[0].size(); for(int i=0;i for(int j=0;j int x=i+1,y=j+1; dp[x][y]=max(dp[x-1][y],dp[x][y-1])+g[i][j]; } } return dp[n][m]; } 方式二 使用dfs深度优先算法进行深度遍历，但是时间超时，仅供参考。 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param grid int整型vector * @return int整型 */ int res = 0; int maxValue(vector dfs(grid, 0, 0, 0); return res; } void dfs(vector if (x == grid.size() && y == grid[0].size()) { res = max(res, sum); return; } else if (x == grid.size()) { dfs(grid, x, y + 1, sum); } else if (y == grid[0].size()) { dfs(grid, x + 1, y, sum); } else { dfs(grid, x + 1, y, sum + grid[x][y]); dfs(grid, x, y + 1, sum + grid[x][y]); } return; } }; 相关阅读
发表评论