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]
}

别卷了

别卷了