• Leetcode 3363. Find the Maximum Number of Fruits Collected
  • 1. 解題思路
  • 2. 代碼實(shí)現(xiàn)

• 題目鏈接：3363. Find the Maximum Number of Fruits Collected

1. 解題思路

這一題是一道陷阱題……

乍一眼看過去，由于三人的路線完全可能重疊，因此需要考慮路線當(dāng)中果子是否有被取走的情況，就會(huì)變得異常復(fù)雜，完全想不到解答的思路。

但是后續(xù)仔細(xì)一看題目，要求三人都必須在$n?1$步之后走到點(diǎn)$(n?1,n?1)$，因此這道題就被大大簡(jiǎn)化了，因?yàn)?#xff1a;

• 對(duì)于第一個(gè)孩子而言，雖然可走的路線非常多，但是要求$n?1$步之后走到點(diǎn)$(n?1,n?1)$，他能走的路線事實(shí)上也就是沿著對(duì)角線的最短路線了；
• 對(duì)于第二個(gè)孩子，由于終點(diǎn)必須走到點(diǎn)$(n?1,n?1)$，因此事實(shí)上他最遠(yuǎn)能走到的位置也就是對(duì)角線的位置，而由于對(duì)角線上的果子必然都被第一個(gè)孩子拿走了，因此他事實(shí)上只會(huì)在對(duì)角線的上方行走，只有在最后一步會(huì)走到$(n?1,n?1)$。
• 同樣對(duì)于第三個(gè)孩子，出于同樣的限制條件，他事實(shí)上也只會(huì)在對(duì)角線下方行走，且最后一步會(huì)走到$(n?1,n?1)$。

因此，事實(shí)上三人的路線是完全不會(huì)重合的，或者說最優(yōu)方案中三人的路線必然不重合，因此我們只需要分別獨(dú)立考察第二和第三個(gè)孩子的最優(yōu)路線即可，而這就是兩個(gè)簡(jiǎn)單的動(dòng)態(tài)規(guī)劃的問題了。

2. 代碼實(shí)現(xiàn)

給出python代碼實(shí)現(xiàn)如下：

class Solution:def maxCollectedFruits(self, fruits: List[List[int]]) -> int:n = len(fruits)s1 = sum(fruits[i][i] for i in range(n))@lru_cache(None)def dp1(i, j):if i == n-2 and j == n-1:return fruits[i][j]ans = -math.inffor k in range(j-1, j+2):if k < n and k > i:ans = max(ans, fruits[i][j] + dp1(i+1, k))return ans@lru_cache(None)def dp2(i, j):if i == n-1 and j == n-2:return fruits[i][j]ans = -math.inffor k in range(i-1, i+2):if k < n and k > j:ans = max(ans, fruits[i][j] + dp2(k, j+1))return ansreturn s1 + dp1(0, n-1) + dp2(n-1, 0)

提交代碼評(píng)測(cè)得到：耗時(shí)1946ms，占用內(nèi)存297.3MB。