1937. Maximum Number of Points with Cost
有m*n的矩陣
要在每一列的挑一個數字，將這些數字相加
若是上下兩列的行數不同就要減去行數差
假設是points[r1][c1]、points[r1+1][c2]
就要減去abs(c1,c2)
請問可以得到的最大總和是多少?
思路:
沒想法的話
可以先去看這一題1014. Best Sightseeing Pair
用一個dp矩陣去紀錄
其中dp[i]代表這一列第i行最大的總和
就由左到右和由右到左去去紀錄最大值
maxnum=max(maxnum-1,points[i])
這樣就可以得到答案了
golang code :
func maxPoints(points [][]int) int64 {
n, m := len(points), len(points[0])
maxtoright, maxtoleft := 0, 0
dp := make([]int, m)
for i := 0; i < n-1; i++ {
maxtoright, maxtoleft = 0, 0
for j := 0; j < m; j++ {
maxtoleft = max(maxtoleft-1, points[i][m-j-1])
maxtoright = max(maxtoright-1, points[i][j])
dp[j] = max(dp[j], maxtoright)
dp[m-1-j] = max(dp[m-1-j], maxtoleft)
}
for j := 0; j < m; j++ {
points[i+1][j] += dp[j]
}
}
ans := 0
for i := 0; i < m; i++ {
ans = max(ans, points[n-1][i])
}
return int64(ans)
}
func max(i, j int) int {
if i > j {
return i
}
return j
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.72.101.78 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1723892458.A.497.html