数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法学研究C++中的樱桃采摘
假设我们有一个 N x N 的网格，网格中充满了樱桃。每个单元格包含以下可能的整数之一：
- 0 - 表示单元格为空，可以通行
- 1 - 表示单元格包含一颗樱桃，可以拾取并通行
- -1 - 表示单元格包含荆棘，阻挡道路
我们必须遵守以下规则来收集最多的樱桃：
- 从位置 (0, 0) 开始，移动到 (N-1, N-1)，只能向右或向下移动到有效的路径单元格。
- 到达 (N-1, N-1) 后，向左或向上移动返回 (0, 0)，只能通过有效的路径单元格。
- 当我们经过包含樱桃的路径单元格时，我们将樱桃拾取，单元格变为空单元格（值为 0）。
- 如果 (0, 0) 和 (N-1, N-1) 之间没有有效的路径，则无法收集任何樱桃。
因此，如果输入如下：
| 0 | 1 | -1 |
| 1 | 0 | -1 |
| 1 | 1 | 1 |
输出将为 5，因为我们从位置 (0, 0) 开始，向下、向下、向右、向右移动到达 (2, 2)。在此次旅行中，我们拾取了 4 颗樱桃，矩阵变为：
| 0 | 1 | -1 |
| 0 | 0 | -1 |
| 0 | 0 | 0 |
然后，我们向左、向上、向上、向左移动返回 (0,0)，拾取一颗樱桃。拾取的樱桃总数为 5。
为了解决这个问题，我们将遵循以下步骤：
- 定义一个大小为 2 x 2 的数组 dir：{{1, 0}, {0, 1}}
- INF := 10^9
- 定义一个大小为 51 x 51 x 51 的数组 dp。
- 定义一个函数 solve()，它将接收 r1、c1、c2、一个二维数组 >& grid，
- n := grid 的大小，r2 := r1 + c1 - c2，ret := 0
- m := (如果 n 非零，则为 grid[0] 的大小，否则为 0)
- 如果 r1 < 0 或 c1 < 0 或 r2 < 0 或 c2 < 0 或 r1 >= n 或 r2 >= n 或 c1 >= m 或 c2 >= m，则：
- 返回 -INF
- 如果 grid[r1, c1] 等于 -1 或 grid[r2, c2] 等于 -1，则：
- 返回 -INF
- 如果 r1 等于 r2 且 c1 等于 c2 且 r1 等于 n - 1 且 c1 等于 m - 1，则：
- 返回 grid[r1, c1]
- 如果 dp[r1, c1, c2] 不等于 -1，则：
- 返回 dp[r1, c1, c2]
- ret := ret + grid[r1, c1]
- 如果 r1 等于 r2 且 c1 等于 c2，则：什么也不做
- 否则
- ret := ret + grid[r2, c2]
- temp := -INF
- 对于初始化 k := 0，当 k < 2 时，更新（k 增加 1），执行：
- temp := temp 和 solve(r1 + dir[k, 0], c1 + dir[k, 1], c2 + 1, grid) 的最大值
- temp := temp 和 solve(r1 + dir[k, 0], c1 + dir[k, 1], c2, grid) 的最大值
- 返回 dp[r1, c1, c2] = ret + temp
- 在主方法中，执行以下操作：
- 用 -1 填充 dp
- ret := solve(0, 0, 0, grid)
- 返回 0 和 ret 的最大值
让我们来看下面的实现，以便更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
int dir[2][2] = {{1, 0}, {0, 1}};
const int INF = 1e9;
class Solution {
public:
int dp[51][51][51];
int solve(int r1, int c1, int c2, vector < vector <int> >& grid){
int n = grid.size();
int r2 = r1 + c1 - c2;
int ret = 0;
int m = n? grid[0].size() : 0;
if(r1 < 0 || c1 < 0 || r2 < 0 || c2 < 0 || r1 >= n || r2 >= n || c1 >= m || c2 >= m) return -INF;
if(grid[r1][c1] == -1 || grid[r2][c2] == -1) return -INF;
if(r1 == r2 && c1 == c2 && r1 == n - 1 && c1 == m - 1)return grid[r1][c1];
if(dp[r1][c1][c2] != -1) return dp[r1][c1][c2];
ret += grid[r1][c1];
if(r1 == r2 && c1 == c2){
}else ret += grid[r2][c2];
int temp = -INF;
for(int k = 0; k < 2; k++){
temp = max(temp, solve(r1 + dir[k][0], c1 + dir[k][1], c2 + 1, grid));
temp = max(temp, solve(r1 + dir[k][0], c1 + dir[k][1], c2, grid));
}
return dp[r1][c1][c2] = ret + temp;
}
int cherryPickup(vector<vector<int>>& grid) {
memset(dp, -1, sizeof(dp));
int ret = solve(0, 0, 0, grid);
return max(0, ret);
}
};
main(){
Solution ob;
vector<vector<int>> v = {{0,1,-1},{1,0,-1},{1,1,1}};
cout << (ob.cherryPickup(v));
}输入
{{0,1,-1},{1,0,-1},{1,1,1}}输出
5
更新于：2020年6月2日
350 次浏览
广告