如何将向量作为Map的键实现双整数参数函数的记忆化？

你代码里的核心问题是：数组作为Map的键时，是按引用而非值比较的。每次调用[m,n]都会创建一个全新的数组对象，所以map.has([m,n])永远找不到之前存入的键，记忆化完全失效。

下面是几种不用简单字符串拼接的替代实现方案：

1. 利用参数对称性优化字符串键（推荐） #

因为gridTraveler(m,n)和gridTraveler(n,m)的结果完全相同，先对参数排序再生成字符串键，既能解决引用问题，还能减少一半的缓存条目：

let map = new Map();

function gridTraveler(m, n){
    if (m === 0 || n === 0)
        return 0;
    if (m === 1 && n === 1)
        return 1;
    // 排序后生成唯一键，减少缓存数量
    const key = `${Math.min(m,n)}-${Math.max(m,n)}`;
    if (map.has(key))
        return map.get(key);
    const res = gridTraveler(m-1, n) + gridTraveler(m, n-1);
    map.set(key, res);
    return res;
}

2. 将双整数编码为唯一数字键 #

如果参数的范围可控（比如不超过1e5），可以把两个数合并成一个唯一的整数，用数字作为Map的键：

let map = new Map();

function gridTraveler(m, n){
    if (m === 0 || n === 0)
        return 0;
    if (m === 1 && n === 1)
        return 1;
    // 用大数编码，假设m/n不超过100000，超出范围可换更大的基数或用BigInt
    const base = 100000;
    const key = Math.min(m,n) * base + Math.max(m,n);
    if (map.has(key))
        return map.get(key);
    const res = gridTraveler(m-1, n) + gridTraveler(m, n-1);
    map.set(key, res);
    return res;
}

如果参数可能很大，改用BigInt避免溢出：

const key = BigInt(Math.min(m,n)) * 100000n + BigInt(Math.max(m,n));

3. 自定义缓存结构（小范围场景适用） #

自己实现一个基于值比较的缓存，不用依赖Map的引用比较逻辑，但注意这种方法的查找效率是O(n)，只适合缓存条目较少的情况：

class GridCache {
    #entries = [];

    has(m, n) {
        return this.#entries.some(([keyM, keyN]) => keyM === m && keyN === n);
    }

    get(m, n) {
        const entry = this.#entries.find(([keyM, keyN]) => keyM === m && keyN === n);
        return entry?.[2];
    }

    set(m, n, value) {
        this.#entries.push([m, n, value]);
    }
}

const cache = new GridCache();

function gridTraveler(m, n){
    if (m === 0 || n === 0)
        return 0;
    if (m === 1 && n === 1)
        return 1;
    if (cache.has(m, n))
        return cache.get(m, n);
    const res = gridTraveler(m-1, n) + gridTraveler(m, n-1);
    cache.set(m, n, res);
    return res;
}

4. 对象池复用键对象 #

维护一个对象池，保证相同的m,n复用同一个对象，这样就能用WeakMap或Map正确识别键：

const keyPool = new Map();
const cache = new WeakMap();

// 复用对象，避免重复创建
function getCacheKey(m, n) {
    const sortedStr = `${Math.min(m,n)}-${Math.max(m,n)}`;
    if (!keyPool.has(sortedStr)) {
        keyPool.set(sortedStr, { x: Math.min(m,n), y: Math.max(m,n) });
    }
    return keyPool.get(sortedStr);
}

function gridTraveler(m, n){
    if (m === 0 || n === 0)
        return 0;
    if (m === 1 && n === 1)
        return 1;
    const key = getCacheKey(m, n);
    if (cache.has(key))
        return cache.get(key);
    const res = gridTraveler(m-1, n) + gridTraveler(m, n-1);
    cache.set(key, res);
    return res;
}

内容的提问来源于stack exchange，提问作者rayankb92