→ SecondRun: 到底誰過年還在刷題 02/11 17:49
推 DJYOSHITAKA: 你好猛 02/11 17:52
→ JIWP: 164p欸 好爽 02/11 17:55
1463 Cherry Pickup II
給一個2維矩陣grid，grid[i][j]代表這個格子的櫻桃數量
有兩個機器人會收集格子上的櫻桃
當兩個機器人走到同一格的時候，只有一個機器人可以拿grid[i][j]個櫻桃，另一個拿0個
機器人一個是從左上角grid[0][0]，另一個是從右上角grid[0][cols-1]
每次可以往左下、正下、右下走
請問機器人最多可以收集幾個櫻桃
思路：
建立一個3維dp矩陣
dp[i][j][k]代表第ｉ列，機器人1拿j列，機器人2拿k列的最大數目
機器人1走到[i][j]有3種走法 [i-1][j-1]、[i-1][j]、[i-1][j+1]
同理機器人2走到[i][k]也有三種走法 [i-1][k-1]、[i-1][k]、[i-1][k+1]
這樣總共9種組合
dp[i][j][k]=這9種組合最大的+grid[i][j]+grid[i][k]
最後返回dp[n-1]裡最大的數字就好
Go code
var m int
func cherryPickup(grid [][]int) int {
n := len(grid)
m = len(grid[0])
dp1 := [70][70]int{}
dp2 := [70][70]int{}
dp1[0][m-1] = grid[0][0] + grid[0][m-1]
for i := 1; i < n; i++ {
for j := 0; j <=min(i,m-1); j++ { //j最大會到i但不能超過m
for k := m - 1; k >= max(m-1-i, 0); k-- {//k最小可以到n-1-i但不能
小於0
dp2[j][k] = grid[i][j] + grid[i][k] + cal(&dp1, j, k)
if j == k {
dp2[j][k] -= grid[i][k]
}
}
}
dp1=dp2
dp2 = [70][70]int{}
}
ans := 0
for i := 0; i < m; i++ {
for j := 0; j < m; j++ {
ans = max(ans, dp1[i][j])
}
}
return ans
}
func cal(dp *[70][70]int, x, y int) int {
ans := 0
for i := -1; i <= 1; i++ {
for j := -1; j <= 1; j++ {
if x+i > -1 && x+i < m && y+j > -1 && y+j < m {
ans = max(ans, (*dp)[x+i][y+j])
}
}
}
return ans
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.138.223.153 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1707644561.A.EB7.html