※ 引述《sixB (6B)》之銘言：
: 2140.
: 有點像搶房子
: 不過每間有規定搶了之後要跳過幾格
: 一開始只開3格dp
: 後來發現沒辦法
: 他不是固定跳過一個
: 我就想ㄚ
: 這間搶了 那這個值要跳到哪邊才能再取
: 直接把他擺到後面去 能用的時候再管他
: ##
: dp[i] 不是第i格最大
: 是我現在還沒取i 並且可以取iㄉ最大
: 所以第i格最大是dp[i] + point[i]
學我 看到dp就遞迴
不用管什麼時候要算答案
答案會自己知道什麼時候他會被算出來ㄉ
Java Code:
-----------------------------------------------
class Solution {
int[][] questions;
Long[] memo;
public long mostPoints(int[][] questions) {
this.questions = questions;
this.memo = new Long[questions.length];
return dfs(0);
}
long dfs(int i) {
if (i >= questions.length) {
return 0;
}
if (memo[i] != null) {
return memo[i];
}
return memo[i] = Math.max(
questions[i][0] + dfs(i + 1 + questions[i][1]),
dfs(i + 1)
);
}
}
-----------------------------------------------
--
https://i.imgur.com/pD41PYS.jpeg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.159.104.111 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1743521615.A.A54.html