記錄了初步解題思路 以及本地實現代碼；并不一定為最優 也希望大家能一起探討 一起進步

---

5/6 741. 摘櫻桃

從起點到終點 再返回起點
可以看做兩個人同時從起點到終點走兩條路所能拿到的櫻桃總和
假設兩人同時走了k步 那么坐標為(x1,k-x1) (x2,k-x2)
設dp[k][x1][x2]表示兩人從此時到終點能夠摘到的櫻桃之和最大值
倒序去除掉k 并假設x1<=x2

def cherryPickup(grid):""":type grid: List[List[int]]:rtype: int"""n = len(grid)dp = [[float('-inf')]*n for _ in range(n)]dp[0][0] = grid[0][0]for k in range(1,2*n-1):for x1 in range(min(k,n-1),max(k-n,-1),-1):for x2 in range(min(k,n-1),x1-1,-1):y1,y2=k-x1,k-x2if grid[x1][y1]==-1 or grid[x2][y2]==-1:dp[x1][x2] = float('-inf')continuev = dp[x1][x2]if x1>0:v = max(v,dp[x1-1][x2])if x2>0:v = max(v,dp[x1][x2-1])if x1>0 and x2>0:v = max(v,dp[x1-1][x2-1])v += grid[x1][y1]if x1!=x2:v += grid[x2][y2]dp[x1][x2] = vreturn max(dp[-1][-1],0)

---

5/7 1463. 摘櫻桃 II

矩陣m*n
機器人每走一步必定下一行
所以兩機器人每一步之后都在同一行
dp[k][y1][y2]表示在k行兩個機器人分別在位置(k,y1) (k,y2)情況下能夠得到的最大值
k=0為第一行 y1=0 y2=n-1
遍歷每一行k=1~m-1
當前行增加grid[k][y1]+grid[k][y2]
如果在同一個位置y1=y2那么只加一次
y可以由上一行y-1,y,y+1三個位置走過來
考慮各個位置最大值dp[k][y1][y2]
最后找到dp[m-1][y1][y2]的最大值即可

def cherryPickup(grid):""":type grid: List[List[int]]:rtype: int"""m,n=len(grid),len(grid[0])dp = [[[float("-inf")]*n for _ in range(n)] for _ in range(m)]dp[0][0][n-1]=grid[0][0]+grid[0][n-1]for k in range(1,m):for y1 in range(n):for y2 in range(y1,n):v = grid[k][y1]if y1!=y2:v += grid[k][y2]pre = dp[k-1][y1][y2]if y1>0:pre = max(pre,dp[k-1][y1-1][y2])if y2>0:pre = max(pre,dp[k-1][y1-1][y2-1])if y2<n-1:pre = max(pre,dp[k-1][y1-1][y2+1])if y1<n-1:pre = max(pre,dp[k-1][y1+1][y2])if y2>0:pre = max(pre,dp[k-1][y1+1][y2-1])if y2<n-1:pre = max(pre,dp[k-1][y1+1][y2+1])if y2>0:pre = max(pre,dp[k-1][y1][y2-1])if y2<n-1:pre = max(pre,dp[k-1][y1][y2+1])dp[k][y1][y2] = pre+vans = 0for i in range(n):ans = max(ans,max(dp[m-1][i]))return ans

---

5/8 2079. 給植物澆水

依次給植物澆水 如果水不夠了當前位置為x
說明在x-1位置就需要重新灌水
2*x步重新灌水并回到x-1位置
一共n個植物每次一步需要n步

def wateringPlants(plants, capacity):""":type plants: List[int]:type capacity: int:rtype: int"""n=len(plants)cur = capacityans = nfor i in range(n):print(i,cur)if plants[i]<=cur:cur -= plants[i]else:cur = capacity-plants[i]ans +=2*ireturn ans

---

5/9 2105. 給植物澆水 II

模擬兩人澆水 一個從左 一個從右
直到兩人相遇

def minimumRefill(plants, capacityA, capacityB):""":type plants: List[int]:type capacityA: int:type capacityB: int:rtype: int"""n = len(plants)l,r = 0,n-1a,b = capacityA,capacityBans = 0while l<=r:if l==r:if a>=b:if a<plants[l]:ans+=1else:if b<plants[l]:ans+=1breakif a>=plants[l]:a-=plants[l]else:ans +=1a = capacityA-plants[l]if b>=plants[r]:b-=plants[r]else:ans+=1b = capacityB-plants[r]l+=1r-=1return ans

---

5/10 2960. 統計已測試設備

模擬 ans為測試次數

def countTestedDevices(batteryPercentages):""":type batteryPercentages: List[int]:rtype: int"""ans=0for v in batteryPercentages:if v>ans:ans+=1return ans

---

5/11 2391. 收集垃圾的最少總時間

因為垃圾車只能有一輛可以工作
可以看做三種垃圾依次處理
cur記錄三輛車當前位置

def garbageCollection(garbage, travel):""":type garbage: List[str]:type travel: List[int]:rtype: int"""ans = 0cur={"G":0,"P":0,"M":0}for i,g in enumerate(garbage):for v in g:while cur[v]<i:ans += travel[cur[v]]cur[v]+=1ans+=1return ans

---

5/12

---