題目描述
這是 LeetCode 上的 741. 摘櫻桃 郑叠，難度為 困難。
Tag : 「線性 DP」
一個 的網(wǎng)格(
grid) 代表了一塊櫻桃地油吭，每個格子由以下三種數(shù)字的一種來表示：
-
表示這個格子是空的署拟，所以你可以穿過它。
-
表示這個格子里裝著一個櫻桃心包，你可以摘到櫻桃然后穿過它馒铃。
-
表示這個格子里有荊棘，擋著你的路娃殖。
你的任務(wù)是在遵守下列規(guī)則的情況下议谷，盡可能的摘到最多櫻桃：
- 從位置
出發(fā)卧晓，最后到達
，只能向下或向右走逼裆，并且只能穿越有效的格子（即只可以穿過值為
- 當(dāng)?shù)竭_
- 當(dāng)你經(jīng)過一個格子且這個格子包含一個櫻桃時，你將摘到櫻桃并且這個格子會變成空的（值變?yōu)?）纳像；
- 如果在
示例 1:
輸入: grid =
[[0, 1, -1],
[1, 0, -1],
[1, 1, 1]]
輸出: 5
解釋：
玩家從（0,0）點出發(fā)导绷，經(jīng)過了向下走，向下走贾费，向右走檐盟，向右走，到達了點(2, 2)导犹。
在這趟單程中陌宿，總共摘到了4顆櫻桃，矩陣變成了[[0,1,-1],[0,0,-1],[0,0,0]]。
接著掰烟，這名玩家向左走，向上走蝎亚，向上走发框，向左走，返回了起始點梅惯，又摘到了1顆櫻桃。
在旅程中铣减，總共摘到了5顆櫻桃，這是可以摘到的最大值了缔刹。
說明:
-
grid是一個的二維數(shù)組劣针，N的取值范圍是
- 每一個
grid[i][j]都是集合{-1, 0, 1}其中的一個數(shù) - 可以保證起點
grid[0][0]和終點grid[N-1][N-1]的值都不會是
線性 DP
為了方便捺典，我們令 grid 為 g，同時調(diào)整矩陣橫縱坐標(biāo)從 開始肝箱。
原問題為先從左上角按照「只能往下 + 只能往右」的規(guī)則走到右下角稀蟋，然后再按照「只能往上 + 只能往左」的規(guī)則走回左上角，途徑的值為 的格子得一分（只能得分一次骏融，得分后置零）萌狂，同時不能經(jīng)過值為
的格子茫藏。
其中第二趟的規(guī)則等價于按照第一趟的規(guī)則從左上角到右下角再走一遍，再結(jié)合每個位置的只能得分一次凉当，可以將原問題等價于：兩個點從左上角開始同時走，最終都走到右下角的最大得分看杭。
定義 為當(dāng)前走了
步（橫縱坐標(biāo)之和）楼雹，且第一個點當(dāng)前在第
行，第二點在第
行時的最大得分榨咐，最終答案為
携悯，同時有
的起始狀態(tài)。
由于兩個點是同時走（都走了 步）龟劲，結(jié)合「只能往下 + 只能往右」的規(guī)則轴或，可直接算得第一個點所在的列為
照雁，第二點所在的列為
。
不失一般性考慮 該如何轉(zhuǎn)移萍诱，兩個點均有可能走行或走列污呼，即有
種前驅(qū)狀態(tài)：
、
籍凝、
和
，在四者中取最大值饵蒂，同時當(dāng)前位置
和
的得分需要被累加酱讶，假設(shè)兩者得分別為
和
，若兩個位置不重疊的話得问，可以同時累加软免，否則只能累加一次。
一些細(xì)節(jié)：為了防止從值為 的格子進行轉(zhuǎn)移影響正確性漓骚，我們需要先將所有
初始化為負(fù)無窮榛泛。
代碼：
class Solution {
static int N = 55, INF = Integer.MIN_VALUE;
static int[][][] f = new int[2 * N][N][N];
public int cherryPickup(int[][] g) {
int n = g.length;
for (int k = 0; k <= 2 * n; k++) {
for (int i1 = 0; i1 <= n; i1++) {
for (int i2 = 0; i2 <= n; i2++) {
f[k][i1][i2] = INF;
}
}
}
f[2][1][1] = g[0][0];
for (int k = 3; k <= 2 * n; k++) {
for (int i1 = 1; i1 <= n; i1++) {
for (int i2 = 1; i2 <= n; i2++) {
int j1 = k - i1, j2 = k - i2;
if (j1 <= 0 || j1 > n || j2 <= 0 || j2 > n) continue;
int A = g[i1 - 1][j1 - 1], B = g[i2 - 1][j2 - 1];
if (A == -1 || B == -1) continue;
int a = f[k - 1][i1 - 1][i2], b = f[k - 1][i1 - 1][i2 - 1], c = f[k - 1][i1][i2 - 1], d = f[k - 1][i1][i2];
int t = Math.max(Math.max(a, b), Math.max(c, d)) + A;
if (i1 != i2) t += B;
f[k][i1][i2] = t;
}
}
}
return f[2 * n][n][n] <= 0 ? 0 : f[2 * n][n][n];
}
}
- 時間復(fù)雜度：狀態(tài)數(shù)量級為
曹锨，每個狀態(tài)轉(zhuǎn)移復(fù)雜度為
沛简。整體復(fù)雜度為
- 空間復(fù)雜度：
最后
這是我們「刷穿 LeetCode」系列文章的第 No.741 篇，系列開始于 2021/01/01给郊，截止于起始日 LeetCode 上共有 1916 道題目捧灰，部分是有鎖題，我們將先把所有不帶鎖的題目刷完炭庙。
在這個系列文章里面煌寇，除了講解解題思路以外，還會盡可能給出最為簡潔的代碼擦盾。如果涉及通解還會相應(yīng)的代碼模板淌哟。
為了方便各位同學(xué)能夠電腦上進行調(diào)試和提交代碼，我建立了相關(guān)的倉庫：https://github.com/SharingSource/LogicStack-LeetCode 腐碱。
在倉庫地址里，你可以看到系列文章的題解鏈接喂走、系列文章的相應(yīng)代碼谋作、LeetCode 原題鏈接和其他優(yōu)選題解。
更多更全更熱門的「筆試/面試」相關(guān)資料可訪問排版精美的 合集新基地 ????
本文由mdnice多平臺發(fā)布
