我正在解決一個問題：
給定一個整數串列
nums，撰寫一個函式，回傳最大的非相鄰數字之和。數字可以是0負數。對于nums = [5, 1, 1, 5]，輸出應該是10。
我實作的動態編程邏輯如下：
vector<pair<int,int>> dp;
int helper(vector<int>& nums, int i, bool include) {
if(i>=nums.size()) return 0;
pair<int,int> p=dp[i];
if(p.first!=INT_MIN) return p.second;
int maxval=0;
if(include) maxval=nums[i] helper(nums,i 1,false);
maxval=max(maxval,helper(nums,i 1,true));
dp[i]=make_pair(include,maxval);
return maxval;
}
int solve(vector<int>& nums) {
dp.clear();
dp.resize(nums.size(),make_pair(INT_MIN,INT_MIN));
// For all -ve numbers in input, just return `0`, as required.
int ans=max({helper(nums,0,true),helper(nums,0,false),0});
//for(auto& p: dp) {
// cout<<p.first<<" "<<p.second<<"\n";
//}
return ans;
}
當我不做任何記憶時，我得到了正確的答案（所以我認為我的遞回關系是正確的）；但是在如上所述記住它時，我得到了錯誤的答案。
我用于記憶的邏輯：對于第ith 值，存盤 a pair<int,int>in dp[i]，其中 pair 的第一個值表示布林值include，而 pair 的第二個值表示為andmaxvalue的當前值計算的結果。請注意，我將 an用于 a ，因為我需要三個值：和“尚未計算”。iincludeintbooltruefalse
我在記憶步驟中缺少什么？有什么更好的方法可以讓我記住它嗎？
謝謝。
uj5u.com熱心網友回復：
不要想太多。記住f(P) { ... return Expr; }P 是引數元組的函式總是相同的。從元組 P 添加一個外部（不是遞回函式的本地）映射 M 以回傳值。然后將 f 重寫為
f(P) {
if M contains key P, return M[P];
...
t = Expr;
M[P] = t;
return t;
}
它看起來像在你的函式中，nums永遠不會改變。所以你可以從 P 中省略它。如果剩下的引數是 anint和 a bool，并且函式回傳int，那么鍵元組有型別<int, bool>，并且映射回傳int。那就是map<tuple<int, bool>, int>。
如果映射鍵最終是一個自然數，并且可能的范圍很小，那么您可以將備忘錄映射替換為一個陣列，該陣列初始化為一個表示“無值”的值。然后“包含密鑰”測驗變成了檢查 M[P] 是否不同于“無值”。在實際問題中，這并不經常發生。
我會讓你解決剩下的，因為看起來你正在學習。需要注意的是，在正確的實作中，您不會將地圖設為全域變數。您將遞回方法包裝在一個類中，并使nums備忘錄快取這兩個欄位，因此它們不需要作為引數傳遞。
uj5u.com熱心網友回復：
int solve(const vector<int>& nums) {
int N = nums.size();
vector<int> dp(N, INT_MIN);
function<int(int)> iter = [&](int i) {
if(i>=N) { return 0; }
if(dp[i] != INT_MIN) { return dp[i]; }
return dp[i] = max(nums[i] iter(i 2), iter(i 1));
};
return iter(0);
}
uj5u.com熱心網友回復：
掃描陣列，記錄三個最大的數字及其位置。如果較大的兩個不相鄰，那么它們的總和就是答案。如果較大的兩個相鄰，則 (#1 #3) 或 (#2 #3) 將是答案，具體取決于哪個更大。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/468476.html
下一篇：如何獲取所有其他單選按鈕的檢查值