資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告