我目前正致力于在 Grid Traveler 問題中實作 memoization。看起來它應該可以作業，但它仍然堅持在更大的情況下，比如 (18,18)。我錯過了什么，或者地圖不是這類問題的正確選擇嗎？
PS我在使用地圖方面還是很陌生。
#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;
uint64_t gridTravMemo(int m, int n, unordered_map<string, uint64_t>grid)
{
string key;
key = to_string(m) "," to_string(n);
if (grid.count(key) > 0)
return grid.at(key);
if (m == 1 && n == 1)
return 1;
if (m == 0 || n == 0)
return 0;
grid[key] = gridTravMemo(m-1, n, grid) gridTravMemo(m, n-1, grid);
return grid.at(key);
}
int main()
{
unordered_map<string, uint64_t> gridMap;
cout << gridTravMemo(1, 1, gridMap) << endl;
cout << gridTravMemo(2, 2, gridMap) << endl;
cout << gridTravMemo(3, 2, gridMap) << endl;
cout << gridTravMemo(3, 3, gridMap) << endl;
cout << gridTravMemo(18, 18, gridMap) << endl;
return 0;
}
uj5u.com熱心網友回復：
記憶搜索的重點是通過回傳您計算的任何先前值來優化運行時間。這樣，您可以達到O(N*M).
但是，您將unordered_map<string, uint64_t>grid作為引數傳遞給您的深度優先搜索。
您正在呼叫grid[key] = gridTravMemo(m-1, n, grid) gridTravMemo(m, n-1, grid);這意味著您的搜索分為兩個分支。但是，grid在這兩個分支中是不同的。這意味著可以在兩個單獨的分支中訪問相同的狀態，從而導致運行時更像O(2^(N*M)).
當您測驗 18x18 網格時，這絕對不會運行得足夠快。
這相對容易修復。只需宣告grid為全域變數。這樣，它的值可以在不同的分支之間使用。
嘗試這樣的事情：
#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;
unordered_map<string, uint64_t> grid;
uint64_t gridTravMemo(int m, int n)
{
string key;
key = to_string(m) "," to_string(n);
if (grid.count(key) > 0)
return grid.at(key);
if (m == 1 && n == 1)
return 1;
if (m == 0 || n == 0)
return 0;
grid[key] = gridTravMemo(m-1, n) gridTravMemo(m, n-1);
return grid.at(key);
}
int main()
{
cout << gridTravMemo(1, 1) << endl;
grid.clear()
cout << gridTravMemo(2, 2) << endl;
grid.clear()
cout << gridTravMemo(3, 2) << endl;
grid.clear()
cout << gridTravMemo(3, 3) << endl;
grid.clear()
cout << gridTravMemo(18, 18) << endl;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/479437.html
上一篇：函式應該回傳新創建物件的指標，還是該物件的unique_ptr？
下一篇：C 11延遲執行緒的執行