所以，我正在嘗試使用遞回 記憶來解決 LCS。
我知道 dp 效率更高，但只是為了理解，我想使用 hashmap 來解決。
APPROACH -> 給定 2 個字串 s1 和 s2，長度分別為 x 和 y。
在正常遞回中，我們會做這樣的事情。
如果 (x==-1 || y==-1) 回傳 0；
if (s1[x] == s2[y]) 回傳 1 lcs(s1, s2, x-1, y-1);
否則回傳最大值（lcs（s1，s2，x-1，y），lcs（s1，s2，x，y-1））；
現在為了實作記憶，我將使用 hashmap
hashmap 將是 string 和 int 并且 hashmap 將像這樣存盤：
key -> to_string(x) "@@" to_string(y)
value -> 答案
我使用“@@”只是為了分隔這兩個數字。
所以我的代碼是->：
int lcsRecursiveAndMemorization(std::string S1, std::string S2, std::unordered_map<std::string, int> &um, int x, int y)
{
// if either string is empty
if (x == -1 || y == -1)
{
return 0;
}
// check if it is present already
std::string temp = std::to_string(x) "@@" std::to_string(y);
if (um.find(temp) != um.end())
{
return um[temp];
}
else
{
// check for if both the characters are equal
if (S1[x] == S2[y])
{
// after getting answer store it and then return it.
std::string temp1 = std::to_string(x - 1) "@@" std::to_string(y - 1);
um[temp1] = 1 lcsRecursiveAndMemorization(S1, S2, um, x - 1, y - 1);
return um[temp1];
}
else
{
// store answer for all the cases i.e.,
// for x-1, y and x, y-1
// and for x, y also
std::string temp2 = std::to_string(x - 1) "@@" std::to_string(y);
std::string temp3 = std::to_string(x) "@@" std::to_string(y - 1);
int first_ = lcsRecursiveAndMemorization(S1, S2, um, x - 1, y);
int second_ = lcsRecursiveAndMemorization(S1, S2, um, x, y - 1);
// storing
um[temp2] = first_;
um[temp3] = second_;
um[temp] = std::max(first_, second_);
return um[temp];
}
}
}
int main()
{
std::string S2 = "pmjghexybyrgzczy";
std::string S1 = "hafcdqbgncrcbihkd";
int x = S1.size() - 1;
int y = S2.size() - 1;
std::unordered_map<std::string, int> um;
cout << "The LCS length using recursion memorization is -> " << lcsRecursiveAndMemorization(S1, S2, um, x, y) << "\n";
return 0;
}
那么這段代碼有什么問題呢？
對我來說它看起來很好。
它對小字串給出了正確的答案，但對于大字串，答案是錯誤的。
它以未定義的方式運行，就像上面兩個字串一樣，正確答案是 4。
我的程式給出 5，但是......如果我們將 s1 與 s2 交換，它會給出正確答案，即 4？如何？
我的意思是如果我們交換 2 個刺，這不應該影響答案。
我只是將遞回代碼更改為使用 hashmap 進行遞回 記憶。
我不知道為什么它不起作用，我想有一些邏輯問題。
uj5u.com熱心網友回復：
我沒有檢查您的代碼的邏輯，但是如果您想記住與一對整數關聯的結果，為什么不使用二維陣列（或向量，如果您愿意）而不是哈希表？當然它看起來像 DP，但也許是因為它是同一件事 :) 如果你真的想堅持使用地圖，也許至少使用std::pair<int,int>作為鍵，并嘗試看看你的結果是否與 不同std::map，這是一個可能的原因您的代碼可能無法正常作業，因為哈希表總是存在沖突的風險。
PS：這些行um[temp2] = first_; um[temp3] = second_;應該沒有用，因為您已經在呼叫lcsRecursiveAndMemorization(S1, S2, um, x - 1, y)and結束時存盤了這些結果lcsRecursiveAndMemorization(S1, S2, um, x, y - 1)。
uj5u.com熱心網友回復：
是的，確實邏輯是錯誤的。
新代碼如下所示->
int lcsRecursiveAndMemorization(std::string S1, std::string S2, std::unordered_map<std::string, int> &um, int x, int y){
// if either string is empty
if (x == -1 || y == -1)
{
return 0;
}
// check if it is present already
std::string temp = std::to_string(x) "@@" std::to_string(y);
if (um.find(temp) != um.end())
{
return um[temp];
}
else
{
// check for if both the characters are equal
if (S1[x] == S2[y])
{
// after getting answer store it and then return it.
// std::string temp1 = std::to_string(x - 1) "@@" std::to_string(y - 1);
um[temp] = 1 lcsRecursiveAndMemorization(S1, S2, um, x - 1, y - 1);
return um[temp];
}
else
{
// store answer for all the cases i.e.,
// for x-1, y and x, y-1
// and for x, y also
// std::string temp2 = std::to_string(x - 1) "@@" std::to_string(y);
// std::string temp3 = std::to_string(x) "@@" std::to_string(y - 1);
int first_ = lcsRecursiveAndMemorization(S1, S2, um, x - 1, y);
int second_ = lcsRecursiveAndMemorization(S1, S2, um, x, y - 1);
// storing
// um[temp2] = first_;
// um[temp3] = second_;
um[temp] = std::max(first_, second_);
return um[temp];
// return std::max(first_, second_);
}
}}
問題在于如何存盤資料
字串 temp1、temp2、temp3 無用。
我們只需要字串 temp。因為每個子問題都會回傳主要問題的答案。
更新的代碼是不言自明的。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/532375.html
標籤：算法C 14动态规划