作者:
sixB (6B)
2025-04-01 23:05:152140.
有點像搶房子
不過每間有規定搶了之後要跳過幾格
一開始只開3格dp
後來發現沒辦法
他不是固定跳過一個
我就想ㄚ
這間搶了 那這個值要跳到哪邊才能再取
直接把他擺到後面去 能用的時候再管他
##
dp[i] 不是第i格最大
是我現在還沒取i 並且可以取iㄉ最大
所以第i格最大是dp[i] + point[i]
##
using ll = long long;
class Solution {
public:
long long mostPoints(vector<vector<int>>& q) {
// rob house
int n = q.size();
vector<ll> dp(n, 0);
ll cur_mx = 0, mx = 0;
for(int i = 0; i < n; i++){
cur_mx = max(cur_mx, dp[i]);
dp[i] = cur_mx;
ll p = q[i][0] + dp[i], offset = q[i][1] + 1;
mx = max(mx, p);
if(i + offset < n){
dp[i + offset] = max(p, dp[i + offset]);
}
}
return mx;
}
};
一遍過ㄟ連分號都沒有忘記直接ac
我真的好厲害><
solution每個都倒著做好怪
感覺都gpt
愛了
想叫gpt幫我把扣轉成吉卜力風格