今天 (2/11) 的 Daily 是 Hard 題： Leetcode 1463. Cherry Pickup II

目錄

題目分析

題目

You are given a rows x cols matrix grid representing a field of cherries where grid[i][j] represents the number of cherries that you can collect from the (i, j) cell.

You have two robots that can collect cherries for you:

  • Robot #1 is located at the top-left corner (0, 0), and

  • Robot #2 is located at the top-right corner (0, cols - 1). Return the maximum number of cherries collection using both robots by following the rules below:

  • From a cell (i, j), robots can move to cell (i + 1, j - 1), (i + 1, j), or (i + 1, j + 1).

  • When any robot passes through a cell, It picks up all cherries, and the cell becomes an empty cell.

  • When both robots stay in the same cell, only one takes the cherries.

  • Both robots cannot move outside of the grid at any moment.

  • Both robots should reach the bottom row in grid.

給你一個 rows x cols的矩陣 grid 來表示一塊櫻桃田。grid 中每個格子的數字表示你能獲得的櫻桃數目。

你有兩個機器人幫你收集櫻桃，機器人1 從左上角格子(0,0)出發，機器人2 從右上角格子(0, cols-1)出發。

請你依照以下規則，返回兩個機器人能收集的最多櫻桃數目：

  • 從格子 (i,j)出發，機器人可以移動到格子 (i+1, j-1)，(i+1, j)或者 (i+1, j+1) 。
  • 當一個機器人經過某個格子時，它會把該格子內所有的櫻桃都摘走，然後這個位置會變成空格子，即沒有櫻桃的格子。
  • 當兩個機器人同時到達同一個格子時，它們中只有一個可以摘到櫻桃。
  • 兩個機器人在任意時刻都不能移動到grid 外面。
  • 兩個機器人最後都要到達 grid 最底下一行。

Example 1:

alt text

Input: grid = [
    [3,1,1],
    [2,5,1],
    [1,5,5],
    [2,1,1]
]
Output: 24

Explanation: Path of robot #1 and #2 are described in color green and blue respectively.
Cherries taken by Robot #1, (3 + 2 + 5 + 2) = 12.
Cherries taken by Robot #2, (1 + 5 + 5 + 1) = 12.
Total of cherries: 12 + 12 = 24.

Example 2:

alt text

Input: grid = [
    [1,0,0,0,0,0,1],
    [2,0,0,0,0,3,0],
    [2,0,9,0,0,0,0],
    [0,3,0,5,4,0,0],
    [1,0,2,3,0,0,6]
]
Output: 28

Explanation: Path of robot #1 and #2 are described in color green and blue respectively.
Cherries taken by Robot #1, (1 + 9 + 5 + 2) = 17.
Cherries taken by Robot #2, (1 + 3 + 4 + 3) = 11.
Total of cherries: 17 + 11 = 28.

Constraints:

rows == grid.length
cols == grid[i].length
2 <= rows, cols <= 70
0 <= grid[i][j] <= 100

分析

alt text

稍微總結一下題目：

  1. 給定一個矩陣，兩個機器人分別自矩陣的左上與右上出發。

  2. 每一步機器人可以往自己的左下、下、右下，三格之中的任意一格移動，但不可移出邊界。最終機器人必定移動到最下一列。

  3. 機器人每進入一格，就可以獲得格子內的櫻桃。但兩個機器人走到同一格時，僅有一個機器人可以獲得櫻桃。

  4. 返回所有路徑之中，兩個機器人一共取得的櫻桃總數中最大者。

本題的解題關鍵在於，兩個機器人每一步都必定往下移動一列。如果我們讓兩個機器人「同時」移動一步，則他們仍然在下方的同一列中。這讓我們得以簡化複雜的情境。

動態規劃的精神就是化繁為簡，既然「雙機器人」有些難以思考，不如先考慮「單機器人」時的解題策略。

首先，我們先把命題簡化成只有一位機器人，來想想如何用動態規劃解答

解題思路

簡化題：只有一個機器人

簡化題解題策略

來個最簡單的例子：假設這個矩陣只有2x3，且機器人從第一列的中間出發：

alt text

答案是7：選擇底下三格中最大的3，再加上起點的4。

那麼再加上一列看看吧！

alt text

  1. 首先，探討「從第二列出發」，並且分別計算從第二列的每一格出發所能得到的最多分數。

    • 從左邊的7出發，可以選擇1或者2，最佳為7+2=9
    • 從中間的4出發，可以選擇1或2或3，最佳為4+3=7
    • 從右邊的3出發，可以選擇2或3，最佳為3+3=6

  2. 接著，把第二列的分數更新為第一步所計算出的分數，並且移除第三列。換言之，第二列變為最後一列了！

alt text

  1. 最後再計算從第一列出發的最佳解，也就是4+9=13，得到最後的答案。

簡化題動態規劃

透過以上討論，可知動態規劃的每一個子問題就是計算某一步，並且假設下一列為最後一列，並且從矩陣的底部往上計算。

  1. 以solve(i,j)代表：機器人從grid[i][j]這格出發、往下走到底能所獲得的最多櫻桃數，則：

    solve(i,j) = grid[i][j] + max(solve(i+1,j-1), solve(i+1,j), solve(i+1, j+1))

  2. 題目所求為solve(0,0) (假設機器人從左上角出發)

  3. 計算時加上邊界條件：

    • 若 i == len(grid) - 1，代表機器人已經走到底，因此僅能獲得該格的櫻桃，無法往下繼續採集。即：

      solve(i,j) = grid[i][j]

    • 不得走出左右邊界，因此

      solve(i,j)的 0 <= j < len(grid[0])

簡化題範例程式碼 (Python 3)

class Solution:
    def cherryPickup(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        
        @cache 
        def solve(i,j):
            if j==-1 or j==cols: return 0    # 左右邊界
            if i==rows-1: return grid[i][j]  # 底部
            return grid[i][j] + max(solve(i+1, k) for k in range(j-1,j+2))

        return solve(0,0)

這類型的動態規劃題，筆者(on Python 3)比較喜歡用Top-Down撰寫。

主要的原因：

  1. 邊界條件可以直接用return去處理，如果換成bottom-up DP，需要在迴圈中寫一堆邊界判斷很麻煩
  2. 也不需要建立陣列，@cache 高階函式會自動紀錄子問題的答案
  3. 遞迴條件單純，debug不會太麻煩

不過見仁見智，畢竟Top-Donw的時間空間通常都比Bottom-up差。如果是追求Time>99%的話，大多數的情況還是得用top-down去節省時間。

Leetcode 931. Minimum Falling Path Sum和我們這裡舉例的簡化題幾乎相同，差別只在於求的不是max而是min。想熟悉DP的話也可以練習一下

本題的解決策略

思考完了簡化題，回到本題「雙機器人」的情境。先回顧一下前面分析問題時抓到的重點：

兩個機器人的每一步都必定往下走一列，因此兩個機器人的「同一步」可以做為動態規劃的「同一個子問題」來思考。

換言之，本問題和簡化題，在本質上完全相同。只是在簡化題中，我們一次獲得一格的分數，而在本問題中我們一次獲得兩格的分數。

動態規劃是個很有趣的策略，雖然題型可謂千變萬化，但對於「本質相同」的問題，可以使用完全相同的解決策略。

在簡化題中，我們使用j來記錄機器人的橫坐標，並且以機器人每走一步(i+=1)作為一個子問題來思考。

在本問題中，有兩個機器人，那複製這個策略可行嗎？

使用j1、j2來分別記錄兩個機器人的橫坐標，並且以兩個機器人同時走一步(i+=1)作為一個子問題來思考

這個方案是行得通的，只需要再多考慮一個本問題額外的限制：

當兩個機器人同時到達同一個格子時，它們中只有一個可以摘到櫻桃。

處理「走到同一格」的條件限制

  1. 一個簡單的想法是加入條件判斷：

    若兩個機器人走到同一格(j1==j2)，那麼其中一個便無法獲得grid[i][j1]的櫻桃，而是獲得0。

  2. 如果要再優化，可以思考一下：

    在最後的答案，也就是「能獲得最多櫻桃的路徑」中，兩個機器人有可能走到同一格嗎？

    答案是否定的。

    當兩個機器人走到同一格，則其中一個機器人在這格獲得了0分。在題目的測資中，矩陣的值並沒有負數，因此，其中一個機器人只要走到旁邊的格子，就能在這一步額外獲得>=0的櫻桃。

    換言之，在計算的過程中，可以直接排除所有走到同一格(j1==j2)的情況。

這兩種處理方式的差異在於：

  1. 採用第一種方案時，在該路徑上仍會繼續往下計算
  2. 但採用第二種方案時，則是把j1==j2當成一種額外的邊界條件，出現這個狀況時，直接捨棄這個路徑上的計算，從而節省時間。

優化：排除交錯路線

與前段方案二的概念類似，我們還可以額外做一個優化：假設機器人2從右上出發、機器人1從左上出發，則：

讓機器人2永遠位於機器人1的右邊。

簡單思考之後可以發現，假如機器人1跑到機器人2的右邊，則兩者路徑必定發生交錯。

因為最終的櫻桃數量為兩機器人採集到的櫻桃數量直接相加，因此，所有「交錯路徑」必定可以找到等價的「不交錯路徑」，如下圖：

alt text

結合前段的方案二，可以將 j1>=j2 也視為一種邊界條件直接排除，從而提高效能。

範例程式碼 (Python 3)

class Solution:
    def cherryPickup(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])
        
        @cache 
        def solve(i,j1,j2): # Robot1 位於 (i,j1)， Robot位於 (i,j2)
            if j1==-1 or j2==-1 or j1==cols or j2==cols or j1>=j2: # 排除邊界條件
                return 0 
            if i==rows-1:                                          # 到達底部時 (base case)
                return grid[i][j1]+ grid[i][j2]
            return grid[i][j1] + grid[i][j2] + max(                # recursive case
                solve(i+1, n1, n2) 
                for n1 in range(j1-1, j1+2) for n2 in range(j2-1,j2+2))                                     

        return solve(0, 0, cols-1)

複雜度分析

假設矩陣的列數(i)為 n，行數(j)為 m，則：

Top-down 對所有 0<=i<n、並對所有 0<=j1<j2<m 都計算一次並記錄結果，所以

時間複雜度為 T = O(n x m^2)

空間複雜度為 S = O(n x m^2)

alt text

若採用bottom-up DP，每計算完一步，便可以捨棄掉前一步的紀錄陣列，空間複雜度為O(m^2)

結語

我比較想吃草莓。

感謝你的閱讀，如果有不同的想法或心得，歡迎留言一同討論！