iT邦幫忙

1

動態規劃問題請教 | JavaScript | LeetCode 周賽

  • 分享至 

  • xImage

各位好,小弟在看今天周賽的題目,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);
};

2025/01/13 更新,以下 ChatGPT 回覆:

使用 HashMap 和陣列來暫存值,兩者在性能和適用場景上有以下幾個主要差異:

1. 存取速度

  • HashMap:

    • 平均時間複雜度是 (O(1))(基於雜湊函數的計算和衝突處理)。
    • 最差情況是 (O(n)),當出現嚴重雜湊衝突時。
    • 比起陣列,HashMap 需要更多的計算操作(例如計算雜湊值、處理衝突)。
  • 陣列:

    • 存取速度是 (O(1)),因為可以直接透過索引定位到元素。
    • 陣列是緊密排列的結構,記憶體使用效率高,CPU 快取命中率高,因此存取速度比 HashMap 快。

結論: 在沒有特別需求的情況下,陣列的存取速度會比 HashMap 快。


2. 記憶體使用

  • HashMap:

    • HashMap 需要額外的記憶體來儲存雜湊表結構(例如桶、鍵和值)。
    • 有些實作會為了避免雜湊衝突,進行動態擴容或儲存鏈結結構,進一步增加記憶體負擔。
  • 陣列:

    • 陣列的記憶體分配是連續的,空間效率高。
    • 不需要額外的記憶體來儲存結構或指標。

結論: 陣列的記憶體使用效率通常比 HashMap 高。


3. 彈性與功能性

  • HashMap:

    • 適合用來存儲鍵值對,當需要快速透過鍵存取值時非常方便。
    • 支援動態調整大小,適合用在鍵範圍未知或範圍很大的場景。
  • 陣列:

    • 適合用來存儲有序的數據,當數據量固定且可以透過索引直接存取時效率最高。
    • 尺寸固定(或需要手動擴展),在彈性上不如 HashMap。

結論: HashMap 適合處理非數字索引的情況,陣列則更適合數字索引且結構固定的情況。


4. 適用場景

  • HashMap:

    • 當需要以非數字(例如字串、物件)作為鍵來存取值。
    • 當鍵值對之間的關係重要,或需要快速查找鍵。
  • 陣列:

    • 當需要存儲結構簡單、數量已知且能以數字索引存取的數據。
    • 當性能要求極高且數據存取模式簡單。

綜合比較

特性 HashMap 陣列
存取時間 平均 (O(1)) (O(1))
最差時間複雜度 (O(n)) (O(1))
記憶體效率 较低 较高
使用場景 非數字鍵值快速查找 索引數據快速存取

結論

如果僅僅是用來暫存值,並且可以用數字索引,陣列的效率和記憶體使用率會比 HashMap 更高。但如果需要依賴鍵值對的關係(例如字串作為鍵)或需要更高的彈性,HashMap 會是更合適的選擇。

透過文字比對軟體,可以知道,差異點真的不多,而且map get set看起來時間複雜度都很低,應該都很快才對。

猜測是不是事先一次allocate連續的記憶體出來,所花的時間比較短,而.set則是每次需要才一個一個動態要出來,因為這個時間差異造成的?
suezou iT邦新手 4 級 ‧ 2025-01-13 16:01:25 檢舉
Map 是動態增長的,只有在需要時才新增鍵值,這意味著每次存取或更新時,可能會有額外的資源分配開銷。
harry xie iT邦研究生 1 級 ‧ 2025-01-13 22:12:00 檢舉
感謝兩位給予方向,後來用和記憶體相關的問題詢問 ChatGPT,我把它的回覆貼在問題區~如果它說的沒錯,那就是 hashMap 的確比較慢一點。
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友回答

立即登入回答