2017. Grid Game
思路:
根据题目grid只有两列
而且只能往右、下走
假设第一个人是在grid[0][i]选择往下
那第二个人能得到的点数就是
(1)grid[0][i+1] ~ grid[0][n-1]的总和
(2)grid[1][0] ~ grid[i-1]的总和
上述两个中较大的那个
所以第一个人就是要找到i最小化上述两个总和的最大值
搭配preifx sum就可以得到答案了
golang code :
func gridGame(grid [][]int) int64 {
m := len(grid[0])
prefix := [2][]int{}
prefix[0] = make([]int, m+1)
prefix[1] = make([]int, m+1)
prefix[0][1], prefix[1][1] = grid[0][0], grid[1][0]
for i := 1; i < m; i++ {
prefix[0][i+1] = prefix[0][i] + grid[0][i]
prefix[1][i+1] = prefix[1][i] + grid[1][i]
}
ans := math.MaxInt64
for i := 0; i < m; i++ {
ans = min(ans, max(prefix[1][i], prefix[0][m]-prefix[0][i+1]))
}
return int64(ans)
}