Re: [閒聊] 每日leetcode
3363. Find the Maximum Number of Fruits Collected
今天賭博輸錢, 只好寫每日文來騙一點p幣
思路:
根據題目說的每一個人都會在n-1步的時候抵達終點
那在(0,0)的那個人就只能往對角線走, 所以先把對角線的水果拿走, 並計算總和
再來是在(0,n-1)跟(n-1,0)的人, 他們行走的範圍也是有限制
知道這一點後
基本上就是用dp去計算就好了
golang code :
func maxCollectedFruits(fruits [][]int) int {
n := len(fruits)
ans := 0
dpGet := func(dp [][]int, i, j int) int {
if j >= 0 && j < len(dp[i]) {
return dp[i][j]
}
return 0
}
for i := 0; i < n; i++ {
ans += fruits[i][i]
fruits[i][i] = 0
}
dp1, dp2 := make([][]int, n), make([][]int, n)
dp1[0], dp2[0] = []int{fruits[0][n-1]}, []int{fruits[n-1][0]}
for i := 1; i < n/2; i++ {
dp1[i], dp2[i] = make([]int, i+1), make([]int, i+1)
for j := 0; j <= i; j++ {
dp1[i][j] = fruits[i][n-1-j] + max(dpGet(dp1, i-1, j-1), dpGet(dp1, i-1, j)
, dpGet(dp1, i-1, j+1))
dp2[i][j] = fruits[n-1-j][i] + max(dpGet(dp2, i-1, j-1), dpGet(dp2, i-1, j)
, dpGet(dp2, i-1, j+1))
}
}
if n%2 == 1 {
mid := n / 2
dp1[mid], dp2[mid] = make([]int, mid+1), make([]int, mid+1)
for j := 0; j <= mid; j++ {
dp1[mid][j] = fruits[mid][n-1-j] + max(dpGet(dp1, mid-1, j-1), dpGet(dp1,
mid-1, j), dpGet(dp1, mid-1, j+1))
dp2[mid][j] = fruits[n-1-j][mid] + max(dpGet(dp2, mid-1, j-1), dpGet(dp2,
mid-1, j), dpGet(dp2, mid-1, j+1))
}
}
for i := (n + 1) / 2; i < n; i++ {
size := n - i
dp1[i], dp2[i] = make([]int, size), make([]int, size)
for j := 0; j < size; j++ {
dp1[i][j] = fruits[i][n-1-j] + max(dpGet(dp1, i-1, j-1), dpGet(dp1, i-1, j)
, dpGet(dp1, i-1, j+1))
dp2[i][j] = fruits[n-1-j][i] + max(dpGet(dp2, i-1, j-1), dpGet(dp2, i-1, j)
, dpGet(dp2, i-1, j+1))
}
}
return ans + dp1[n-1][0] + dp2[n-1][0]
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 203.121.235.241 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1754581990.A.986.html
推
08/07 23:53,
4月前
, 1F
08/07 23:53, 1F
推
08/07 23:59,
4月前
, 2F
08/07 23:59, 2F
討論串 (同標題文章)
完整討論串 (本文為第 1494 之 1548 篇)：