题目描述
在一个 m×n 的棋盘的每一格都放有一个礼物,每个礼物都有一定的价值(价值大于 0)。
你可以从棋盘的左上角开始拿格子里的礼物,并每次向右或者向下移动一格直到到达棋盘的右下角。
给定一个棋盘及其上面的礼物,请计算你最多能拿到多少价值的礼物?
注意:
m,n>0
m×n≤1350
样例
输入:
[
[2,3,1],
[1,7,1],
[4,6,1]
]
输出:19
解释:沿着路径 2→3→7→6→1 可以得到拿到最大价值礼物。
这道题我用了三种方法写了一下:
第一种:自己写的,递归DP+记忆化搜索,和滑雪那道题的思路一模一样
第二种:y总写的,循环DP
第三种:自己写的DFS,但是这种会超时,不知道怎么优化;感觉需要记忆化搜索
从时间上来看,有记忆化搜索的会更快。
算法1
(递归DP+记忆化搜索) $O(n^2)$
这道题思路有点像滑雪那道题,如果不加记忆化搜索会TLE
C++ 代码
class Solution {
public:
int getMaxValue(vector<vector<int>>& grid)
{
int h = grid.size() , w=grid[0].size();
pair<int,int> end={h-1,w-1};
vector<vector<int>> visited(h+1, vector<int>(w+1 ,0));
int ans = dp(0,0,end,grid,visited);
return ans;
}
int dx[2]={0,1};
int dy[2]={1,0};
int dp(int x,int y, pair<int ,int> &end,vector<vector<int>> &matrix,vector<vector<int>> &visited)
{
if(visited[x][y] != 0) return visited[x][y];
if(x == end.first && y==end.second) return matrix[x][y];
int res =0;
for(int i=0;i<2;++i)
{
int nx = x+dx[i];
int ny = y+dy[i];
if(nx< matrix.size() && ny < matrix[0].size())
{
int temp = dp(nx,ny,end,matrix,visited) + matrix[x][y];
res = max(res,temp);
}
}
visited[x][y] =res;
return res;
}
};
算法2
(y总:循环DP)
C++ 代码
int getMaxValue(vector<vector<int>>& grid)
{
int n = grid.size(), m = grid[0].size();
vector<vector<int>> f(n+1,vector<int>(m+1));//多开一行,表示最外层
for(int i=1;i<=n;++i)
{
for(int j=1;j<=m;++j)
{
f[i][j] = max(f[i-1][j],f[i][j-1]) + grid[i-1][j-1];
}
}
return f[n][m];
}
算法3
(尝试使用DFS)
这道题我的DFS超时了,不知道如何优化。DFS在本地编译器是可以计算。
C++ 代码
class Solution {
public:
int getMaxValue(vector<vector<int>>& grid)
{
int h = grid.size() , w=grid[0].size();
pair<int,int> start={0,0};
pair<int,int> end={h-1,w-1};
vector<vector<bool>> visited(h, vector<bool>(w));
dfs(start,end,grid,visited);
return ans;
}
int dx[2]={0,1};
int dy[2]={1,0};
vector<pair<int,int>> path;
int res=0;
int ans=0;
void dfs(pair<int,int> &start, pair<int,int> &end,vector<vector<int>> &matrix, vector<vector<bool>> &visited)
{
if(start == end)
{
path.emplace_back(end);
// cout << path.size() <<endl;
for(auto x:path)
{
res += matrix[x.first][x.second];
}
path.pop_back();
ans = max(res,ans);
res =0;
return ;
}
path.emplace_back(start);
visited[start.first][start.second]= true;
for(int i=0;i<2;++i)
{
pair<int,int> cur;
cur.first = start.first+dx[i];
cur.second = start.second+dy[i];
if(cur.first< matrix.size() && cur.second < matrix[0].size() && visited[cur.first][cur.second] ==false)
{
dfs(cur,end,matrix,visited);
}
}
path.pop_back();
visited[start.first][start.second]= false;
}
};