各位好,小弟在看今天周賽的題目,3418. Maximum Amount of Money Robot Can Earn,用了記憶化搜索 DFS。
但我發現如果我用 hashMap 儲存計算後的結果會超時,但如果用三維陣列反而不會超時,照理來說做儲存和取值的兩個動作時間複雜度是一樣的,反而 DP 在生成時還會跑迴圈 O(grid.length * grid[0].length * 3)
,有人知道究竟是什麼原因導致前者會超時呢?謝謝!
記憶化搜索: 超時 = =,不會過的解法
var maximumAmount = function (grid) {
const cache = new Map();
// n = remain neutralize times
const DFS = (i, j, n) => {
if (i < 0 || j < 0) return -Infinity;
if (i == 0 && j == 0) {
return n > 0 ? Math.max(grid[i][j], 0) : grid[i][j];
}
let key = `${i}-${j}-${n}`;
if (cache.has(key)) return cache.get(key);
let res = Math.max(DFS(i - 1, j, n), DFS(i, j - 1, n)) + grid[i][j];
if (grid[i][j] < 0 && n > 0) {
res = Math.max(res, DFS(i - 1, j, n - 1), DFS(i, j - 1, n - 1));
}
cache.set(`${i}-${j}-${n}`, res);
return res;
};
return DFS(grid.length - 1, grid[0].length - 1, 2);
};
改用 DP 陣列就能過...= = ?:
var maximumAmount = function (grid) {
const DP = new Array(grid.length).fill().map(() => new Array(grid[0].length).fill().map(() => new Array(3).fill(-Infinity)));
const DFS = (i, j, n) => {
if (i < 0 || j < 0) return -Infinity;
if (i == 0 && j == 0) {
return n > 0 ? Math.max(grid[i][j], 0) : grid[i][j];
}
if (DP[i][j][n] !== -Infinity) return DP[i][j][n];
let res = Math.max(DFS(i - 1, j, n), DFS(i, j - 1, n)) + grid[i][j];
if (grid[i][j] < 0 && n > 0) {
res = Math.max(res, DFS(i - 1, j, n - 1), DFS(i, j - 1, n - 1));
}
DP[i][j][n] = res;
return res;
};
return DFS(grid.length - 1, grid[0].length - 1, 2);
};
使用 HashMap 和陣列來暫存值,兩者在性能和適用場景上有以下幾個主要差異:
HashMap:
陣列:
結論: 在沒有特別需求的情況下,陣列的存取速度會比 HashMap 快。
HashMap:
陣列:
結論: 陣列的記憶體使用效率通常比 HashMap 高。
HashMap:
陣列:
結論: HashMap 適合處理非數字索引的情況,陣列則更適合數字索引且結構固定的情況。
HashMap:
陣列:
特性 | HashMap | 陣列 |
---|---|---|
存取時間 | 平均 (O(1)) | (O(1)) |
最差時間複雜度 | (O(n)) | (O(1)) |
記憶體效率 | 较低 | 较高 |
使用場景 | 非數字鍵值快速查找 | 索引數據快速存取 |
如果僅僅是用來暫存值,並且可以用數字索引,陣列的效率和記憶體使用率會比 HashMap 更高。但如果需要依賴鍵值對的關係(例如字串作為鍵)或需要更高的彈性,HashMap 會是更合適的選擇。