741. 摘櫻桃 : 經典線性 DP 運用題

題目描述

這是 LeetCode 上的 ​​741. 摘櫻桃​​ ，難度為 困難。

Tag : 「線性 DP」

一個 的網格( ​​

​grid​

​) 代表了一塊櫻桃地，每個格子由以下三種數字的一種來表示：

你的任務是在遵守下列規則的情況下，盡可能的摘到最多櫻桃：

• 從位置出發，最後到達，隻能向下或向右走，并且隻能穿越有效的格子（即隻可以穿過值為或者
• 當到達後，你要繼續走，直到傳回到
• 當你經過一個格子且這個格子包含一個櫻桃時，你将摘到櫻桃并且這個格子會變成空的（值變為0）；
• 如果在和

示例 1:

輸入: grid =
[[0, 1, -1],
 [1, 0, -1],
 [1, 1,  1]]

輸出: 5

解釋：
玩家從（0,0）點出發，經過了向下走，向下走，向右走，向右走，到達了點(2, 2)。
在這趟單程中，總共摘到了4顆櫻桃，矩陣變成了[[0,1,-1],[0,0,-1],[0,0,0]]。
接着，這名玩家向左走，向上走，向上走，向左走，傳回了起始點，又摘到了1顆櫻桃。
在旅程中，總共摘到了5顆櫻桃，這是可以摘到的最大值了。      

說明:

• ​

  ​grid​

  ​​ 是一個的二維數組，N的取值範圍是
• 每一個​

  ​grid[i][j]​

  ​​ 都是集合​

  ​{-1, 0, 1}​

  ​ 其中的一個數
• 可以保證起點​

  ​grid[0][0]​

  ​​ 和終點​

  ​grid[N-1][N-1]​

  ​​ 的值都不會是

線性 DP

為了友善，我們令 ​

​grid​

​​ 為 ​

​g​

​​，同時調整矩陣橫縱坐标從

原問題為先從左上角按照「隻能往下 + 隻能往右」的規則走到右下角，然後再按照「隻能往上 + 隻能往左」的規則走回左上角，途徑的值為 的格子得一分（隻能得分一次，得分後置零），同時不能經過值為

其中第二趟的規則等價于按照第一趟的規則從左上角到右下角再走一遍，再結合每個位置的隻能得分一次，可以将原問題等價于：兩個點從左上角開始同時走，最終都走到右下角的最大得分。

定義 為目前走了 步（橫縱坐标之和），且第一個點目前在第 行，第二點在第 行時的最大得分，最終答案為 ，同時有

由于兩個點是同時走（都走了 步），結合「隻能往下 + 隻能往右」的規則，可直接算得第一個點所在的列為 ，第二點所在的列為 。

不失一般性考慮 該如何轉移，兩個點均有可能走行或走列，即有 種前驅狀态：、、 和 ，在四者中取最大值，同時目前位置 和 的得分需要被累加，假設兩者得分别為 和 ，若兩個位置不重疊的話，可以同時累加，否則隻能累加一次。

一些細節：為了防止從值為 的格子進行轉移影響正确性，我們需要先将所有

代碼：

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      

• 時間複雜度：狀态數量級為，每個狀态轉移複雜度為。整體複雜度為
• 空間複雜度：

最後

這是我們「刷穿 LeetCode」系列文章的第 ​

​No.741​

​ 篇，系列開始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道題目，部分是有鎖題，我們将先把所有不帶鎖的題目刷完。

在這個系列文章裡面，除了講解解題思路以外，還會盡可能給出最為簡潔的代碼。如果涉及通解還會相應的代碼模闆。