## [摘櫻桃 II](https://leetcode-cn.com/problems/cherry-pickup-ii/) #### 思路 周賽時放棄了，雖然知道是動態規劃，但是沒有什么思路 **拜讀大佬解法，獲得新思路** * 因為只能向下走，行號具有**后無效性**，可以進行狀態轉移，使用dp * 有兩個機器人還需要使用兩個維度記錄記錄兩個機器人所在的位置 * dp[r][i][j], r為行號，i為Robot#1（以下簡稱R1） 所在的位置，j為Robot#2（以下簡稱R2） 所在的位置 * dp表示走到r行，R1在i位置，R2在j位置，所能摘到的最多的櫻桃數 * **狀態轉移思考:** 對于dp[r][i][j] 想到狀態轉移方程 `$ dp[r][i][j] = max(dp[r-1][k1+i][k2+j]) + (grid[r][i] + grid[r][j]), k1,k2 = -1, 0 ,1 $` **說人話**，就是針對dp[r][i][j]會有3x3，9種可能性從上一行過來。針對當前行，我們不管他上面是怎么走的，反正要想dp[r][i][j]位置獲取的最多，那肯定是從上一行最多的地方過來。然后再加上這一行兩個機器人所在位置的櫻桃數，就是當前位置能夠獲取的最大數量。這樣我們判斷一下最后一行的最大值，就是我們想要的結果。 * 考慮邊界條件，左右兩個機器人，都最多只能再自己的一個三角形區域活動，且不能超過邊界`$ [0,cols) $` 嘗試著寫一下代碼。 AC!，如果dp接觸不多還是需要多思考一下，理解dp的**最優子問題**和**后無效性**條件。 #### 代碼 python3 ``` class Solution: def cherryPickup(self, grid: List[List[int]]) -> int: rows = len(grid) cols = len(grid[0]) dirs = [-1,0,1] dp = [[[0] * cols for _ in range(cols)] for _ in range(rows)] # basecase dp[0][0][-1] = grid[0][0] + grid[0][-1] for r in range(1,rows): # 行號 for i in range(r+1): # 列號,左邊機器人 for j in range(cols-r-1, cols): # 列號,右邊機器人 for ii in dirs: # 9種組合可能性 for jj in dirs: if (i < cols) and (j >= 0) \ and (i + ii >= 0) and (i + ii < cols) \ and (j + jj >= 0) and (j + jj < cols) \ and (i != j): dp[r][i][j] = max(dp[r-1][i+ii][j+jj] + grid[r][i] + grid[r][j], dp[r][i][j]) result = 0 for i in dp[-1]: for j in i: result = max(result, j) return result ```