我為最長的遞增子序列撰寫了一個遞回解決方案，并且效果很好。但是當我在相同的代碼上應用 dp 時，它給出了不同的答案。問題鏈接：https : //practice.geeksforgeeks.org/problems/longest-increasing-subsequence-1587115620/1 遞回代碼：
int LISrecursive(int arr[], int n, int currIndex, int maxVal) {
if (currIndex == n) {
return 0;
}
int included = 0, notIncluded = 0;
if (arr[currIndex] > maxVal) {
included = 1 LISrecursive(arr, n, currIndex 1, arr[currIndex]);
}
notIncluded = LISrecursive(arr, n, currIndex 1, maxVal);
return max(notIncluded, included);
}
DP 代碼：
int LISdp(int arr[], int n, int currIndex, int maxVal, vector<int> &dp) {
if (currIndex == n) {
return 0;
}
if (dp[currIndex] != -1) return dp[currIndex];
int included = 0, notIncluded = 0;
if (arr[currIndex] > maxVal) {
included = 1 LISdp(arr, n, currIndex 1, arr[currIndex], dp);
}
notIncluded = LISdp(arr, n, currIndex 1, maxVal, dp);
return dp[currIndex] = max(notIncluded, included);
}
int32_t main() {
int n;
cin >> n;
int arr[n];
vector<int> dp(n, -1);
for (int i = 0; i < n; i ) {
cin >> arr[i];
}
cout << LISrecursive(arr,n,0,-1);
cout << LISdp(arr, n, 0 , -1, dp);
return 0;
}
我無法弄清楚我做錯了什么？對于這個測驗用例 6 (n) 6 3 7 4 6 9 (arr[]) 遞回代碼給出了 4 個答案（正確） 但是 DP 代碼給出了 3 個答案（錯誤）
uj5u.com熱心網友回復：
當我想到動態規劃時，我通常將其分解為兩個步驟：
與“再次遞回之前不包括當前元素”相比，使用“在再次遞回之前包含當前元素”來解決遞回。這正是您對遞回解決方案所做的。
采用步驟 1 中的遞回解決方案并添加先前計算結果的快取以避免重復遞回。快取可以被概念化為一個多維矩陣，它將傳遞給遞回函式的所有非常量變數引數映射到最終結果。
在您的情況下，每個遞回步驟都有兩個變數currIndex， 和maxVal。 a并且n實際上是整個遞回程序中的常量。遞回步驟的非常量引數的數量是您的快取中的維數。所以你需要一個二維表。我們可以使用一個大的 2-d int 陣列，但這會占用大量記憶體。我們可以使用嵌套的哈希表對實作相同的效率。
您的主要錯誤是，你的快取只有1名維-快取相比，結果currIndex不論價值maxVal。另一個錯誤是使用向量而不是哈希表。您擁有的矢量技術有效，但無法擴展。當我們添加第二個維度時，記憶體使用的規模甚至更糟。
因此，讓我們將快取型別定義為 unordered_map（哈希表），它映射currIndex到另一個映射maxVal到遞回結果的哈希表。您也可以使用元組，但 geeksforgeeks 編碼站點似乎不喜歡那樣。不用麻煩，我們可以定義這個：
typedef std::unordered_map<int, std::unordered_map<int, int>> CACHE;
然后，您的 DP 解決方案實際上只是在遞回函式頂部的 CACHE 中插入查找，并在函式底部的 CACHE 中插入。
int LISdp(int arr[], int n, int currIndex, int maxVal, CACHE& cache) {
if (currIndex == n) {
return 0;
}
// check our cache if we've already solved for currIndex and maxVal together
auto itor1 = cache.find(currIndex);
if (itor1 != cache.end())
{
// itor1->second is a reference to cache[currIndex]
auto itor2 = itor1->second.find(maxVal);
if (itor2 != itor1->second.end())
{
// itor2->second is a reference to cache[n][maxVal];
return itor2->second;
}
}
int included = 0, notIncluded = 0;
if (arr[currIndex] > maxVal) {
included = 1 LISdp(arr, n, currIndex 1, arr[currIndex], cache);
}
notIncluded = LISdp(arr, n, currIndex 1, maxVal, cache);
// cache the final result into the 2-d map before returning
int finalresult = std::max(notIncluded, included);
cache[currIndex][maxVal] = finalresult; // cache the result
return finalresult;
}
然后使用要求解的輸入集的初始呼叫有效地將 INT_MIN 作為初始maxVal和空快取傳遞：
int N = 16
int A[N]={0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15};
CACHE cache;
int result = LISdp(A, N, 0, INT_MIN, cache);
一個小的優化是使a、n和cacheC 類的成員變數封裝您的解決方案，以便它們不必在遞回的每一步都被推入堆疊。快取是通過參考傳遞的，所以這沒什么大不了的。
uj5u.com熱心網友回復：
您的代碼中有兩個問題：
錯誤一
首先在 C 中，陣列的大小必須是編譯時常量。因此，以以下代碼片段為例：
int n = 10;
int arr[n]; //INCORRECT because n is not a constant expression
正確的寫法是：
const int n = 10;
int arr[n]; //CORRECT
同樣，以下（您在代碼示例中所做的）不正確：
int n;
cin >> n;
int arr[n];// INCORRECT because n is not a constant expression
錯誤2
在你的函式中的第二個，在LISdp我看來，沒有必要的宣告
if (dp[currIndex] != -1) return dp[currIndex];//no need for this statement
你應該只洗掉此（以上）陳述句和程式產生預期的輸出4可以看出這里。基本上你沒有想過這個（LISdp 的作業）。您可以使用除錯器查看哪里出錯了。
您的代碼中可能還有其他問題，但到目前為止我能夠發現這兩個問題。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/371653.html
上一篇：遞回地比較兩個串列
下一篇：如何將2個方法回圈在一起？