2140. Solving Questions With Brainpower
dp問題，還是要想好久
dp[i]表示到第i個question時，不包含question[i][0]所能得到的最大值
每次都去更新dp[i]的值
dp[i]=max(dp[i],dp[i-1])
如果拿了question[i][0]這個值，那就跳到i+question[i][1]+1比較
dp[i]+question[i][0]和dp[i+question[i][1]+1]誰比較大
接著每次更新答案找最大的dp[i]+question[i][0]的組合
golang code :
func mostPoints(questions [][]int) int64 {
n, ans := len(questions), 0
dp := make([]int, n+1)
for i := 0; i < n; i++ {
nextIdx := i + questions[i][1] + 1
dp[i+1] = max(dp[i+1], dp[i])
if nextIdx < n {
dp[nextIdx+1] = max(dp[nextIdx+1], dp[i+1]+questions[i][0])
}
ans = max(ans, questions[i][0]+dp[i+1])
}
return int64(ans)
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 203.121.235.241 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1743521219.A.5E2.html