40 篇博文 含有标签「动态规划」

1、题干​

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

进阶：

如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？

致谢：

特别感谢 @pbrother 添加此问题并且创建所有测试用例。

示例 1：

输入：s = "abc", t = "ahbgdc"
输出：true

示例 2：

输入：s = "axc", t = "ahbgdc"
输出：false

提示：

• 0 <= s.length <= 100
• 0 <= t.length <= 10^4
• 两个字符串都只由小写字符组成。

2、思路​

双指针遍历，如果 s 中的字符能全部被消耗完，则结果为 true

3、代码​

function isSubsequence(s: string, t: string): boolean {
    let i = 0, j = 0;

    while (i < s.length && j < t.length) {
        while (j < t.length) {
            if (t[j++] === s[i]) {
                i++;
                break;
            }
        }
    }

    return i === s.length;
};

1、题干​

给你一个由正整数组成的数组 nums 和一个 正 整数 k 。

如果 nums 的子集中，任意两个整数的绝对差均不等于 k ，则认为该子数组是一个 美丽 子集。

返回数组 nums 中 非空 且 美丽 的子集数目。

nums 的子集定义为：可以经由 nums 删除某些元素（也可能不删除）得到的一个数组。只有在删除元素时选择的索引不同的情况下，两个子集才会被视作是不同的子集。

示例 1：

输入：nums = [2,4,6], k = 2
输出：4
解释：数组 nums 中的美丽子集有：[2], [4], [6], [2, 6] 。
可以证明数组 [2,4,6] 中只存在 4 个美丽子集。

示例 2：

输入：nums = [1], k = 1
输出：1
解释：数组 nums 中的美丽数组有：[1] 。
可以证明数组 [1] 中只存在 1 个美丽子集。 

提示：

• 1 <= nums.length <= 20
• 1 <= nums[i], k <= 1000

2、思路​

BFS暴力枚举，时间爆炸，有空再优化，下次一定

3、代码​

function beautifulSubsets(nums: number[], k: number): number {
    const hash = new Array(nums.length).fill(0).map(() => new Array(nums.length).fill(0))
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (Math.abs(nums[j] - nums[i]) === k) hash[i][j] = 1;
        }
    }

    let queue = nums.map((v, i) => [i]), ans = 0;
    while (queue.length) {
        const next = [];
        for (const q of queue) {
            ans++;
            for (let j = q.at(-1) + 1; j < nums.length; j++) {
                if (q.every((i) => !hash[i][j])) next.push([...q, j]);
            }
        }
        queue = next;
    }

    return ans;
};

4、执行结果​

1、题干​

给你一个字符串 s ，它仅包含字符 'a' 和 'b'​​​​ 。

你可以删除 s 中任意数目的字符，使得 s 平衡 。当不存在下标对 (i,j) 满足 i < j ，且 s[i] = 'b' 的同时 s[j]= 'a' ，此时认为 s 是 平衡 的。

请你返回使 s 平衡 的 最少 删除次数。

示例 1：

输入：s = "aababbab"
输出：2
解释：你可以选择以下任意一种方案：
下标从 0 开始，删除第 2 和第 6 个字符（"aababbab" -> "aaabbb"），
下标从 0 开始，删除第 3 和第 6 个字符（"aababbab" -> "aabbbb"）。

示例 2：

输入：s = "bbaaaaabb"
输出：2
解释：唯一的最优解是删除最前面两个字符。

提示：

• 1 <= s.length <= 105
• s[i] 要么是 'a' 要么是 'b'​ 。​

本题跟剑指 Offer II 092. 翻转字符的思路一样

2、思路1​

循环剔除所有 ba 子串并累加剔除次数

3、代码​

function minimumDeletions(s: string): number {
    let ans = 0;
    while (s.includes('ba')) s = s.replace(/ba/g, () => (ans++, ''));
    return ans;
};

4、执行结果​

5、思路2​

思路1实际上是消除所有字符 b 后面的字符 a，可以使用常规遍历模拟消除过程。

具体实现时需要遍历字符串 s 两次，先统计字符 a 的个数，再消除字符 a。

6、代码​

function minimumDeletions(s: string): number {
    let ac = 0;
    for (let i = 0; i < s.length; i++) {
        if (s[i] === 'a') ac++;
    };

    let ans = 0, bc = 0;
    for (let i = 0; ac > 0 && i < s.length; i++) {
        if (s[i] === 'a') bc > 0 ? bc-- : ac--;
        else ans++, bc++, ac--;
    }

    return ans;
};

7、复杂度​

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

8、执行结果​

1、题干​

你将会得到一份单词表 words，一个字母表 letters （可能会有重复字母），以及每个字母对应的得分情况表 score。

请你帮忙计算玩家在单词拼写游戏中所能获得的「最高得分」：能够由 letters 里的字母拼写出的 任意 属于 words 单词子集中，分数最高的单词集合的得分。

单词拼写游戏的规则概述如下：

• 玩家需要用字母表 letters 里的字母来拼写单词表 words 中的单词。
• 可以只使用字母表 letters 中的部分字母，但是每个字母最多被使用一次。
• 单词表 words 中每个单词只能计分（使用）一次。
• 根据字母得分情况表score，字母 'a', 'b', 'c', ... , 'z' 对应的得分分别为 score[0], score[1], ..., score[25]。
• 本场游戏的「得分」是指：玩家所拼写出的单词集合里包含的所有字母的得分之和。

示例 1：

输入：words = ["dog","cat","dad","good"], letters = ["a","a","c","d","d","d","g","o","o"], score = [1,0,9,5,0,0,3,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,0,0,0]
输出：23
解释：
字母得分为  a=1, c=9, d=5, g=3, o=2
使用给定的字母表 letters，我们可以拼写单词 "dad" (5+1+5)和 "good" (3+2+2+5)，得分为 23 。
而单词 "dad" 和 "dog" 只能得到 21 分。

示例 2：

输入：words = ["xxxz","ax","bx","cx"], letters = ["z","a","b","c","x","x","x"], score = [4,4,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,5,0,10]
输出：27
解释：
字母得分为  a=4, b=4, c=4, x=5, z=10
使用给定的字母表 letters，我们可以组成单词 "ax" (4+5)， "bx" (4+5) 和 "cx" (4+5) ，总得分为 27 。
单词 "xxxz" 的得分仅为 25 。

示例 3：

输入：words = ["leetcode"], letters = ["l","e","t","c","o","d"], score = [0,0,1,1,1,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0]
输出：0
解释：
字母 "e" 在字母表 letters 中只出现了一次，所以无法组成单词表 words 中的单词。

提示：

• 1 <= words.length <= 14
• 1 <= words[i].length <= 15
• 1 <= letters.length <= 100
• letters[i].length == 1
• score.length == 26
• 0 <= score[i] <= 10
• words[i] 和 letters[i] 只包含小写的英文字母。

2、思路​

回溯，枚举所有情况计算最高得分。未优化，存在重复计算，效率不高。

3、代码​

function maxScoreWords(words: string[], letters: string[], score: number[]): number {
    const wordScore = new Array(words.length).fill(0);
    for (let i = 0; i < words.length; i++) {
        for (let j = 0; j < words[i].length; j++) {
            wordScore[i] += score[words[i][j].charCodeAt(0) - 97];
        }
    }

    const letterDict = new Array(26).fill(0);
    for (let i = 0; i < letters.length; i++) {
        letterDict[letters[i].charCodeAt(0) - 97] += 1;
    }

    let ans = 0;
    function dfs(sc: number, visited: Set<number>) {
        for (let i = 0; i < words.length; i++) {
            if (visited.has(i)) continue;

            let valid = true;
            for (let j = 0; j < words[i].length; j++) {
                const c = words[i][j].charCodeAt(0) - 97;
                letterDict[c]--;
                if (letterDict[c] < 0) valid = false;
            }

            if (valid) {
                ans = Math.max(ans, sc + wordScore[i]);

                visited.add(i);
                dfs(sc + wordScore[i], visited);
                visited.delete(i);
            }

            for (let j = 0; j < words[i].length; j++) {
                letterDict[words[i][j].charCodeAt(0) - 97]++;
            }
        }
    }

    return dfs(0, new Set()), ans;
};

4、执行结果​

1、题干​

在 x 轴上有一个一维的花园。花园长度为 n，从点 0 开始，到点 n 结束。

花园里总共有 n + 1 个水龙头，分别位于 [0, 1, ..., n] 。

给你一个整数 n 和一个长度为 n + 1 的整数数组 ranges ，其中 ranges[i] （下标从 0 开始）表示：如果打开点 i 处的水龙头，可以灌溉的区域为 [i -  ranges[i], i + ranges[i]] 。

请你返回可以灌溉整个花园的 最少水龙头数目 。如果花园始终存在无法灌溉到的地方，请你返回 -1 。

示例 1：

输入：n = 5, ranges = [3,4,1,1,0,0]
输出：1
解释：
点 0 处的水龙头可以灌溉区间 [-3,3]
点 1 处的水龙头可以灌溉区间 [-3,5]
点 2 处的水龙头可以灌溉区间 [1,3]
点 3 处的水龙头可以灌溉区间 [2,4]
点 4 处的水龙头可以灌溉区间 [4,4]
点 5 处的水龙头可以灌溉区间 [5,5]
只需要打开点 1 处的水龙头即可灌溉整个花园 [0,5] 。

示例 2：

输入：n = 3, ranges = [0,0,0,0]
输出：-1
解释：即使打开所有水龙头，你也无法灌溉整个花园。

提示：

• 1 <= n <= 104
• ranges.length == n + 1
• 0 <= ranges[i] <= 100

写了个奇怪的动态规划思路

2、思路​

用 [i-r,i) 区间的最少水龙头数更新 dp[i]，用 dp[i] 更新 (i,i+r] 区间的最少水龙头数。

dp 数组元素有正负两种状态，正数表示自身可以达到最少水龙头数，负数表示被其他水龙头覆盖达到最少水龙头数；负数在更新 (i,i+r] 区间时需要 +1，正数则不需要。

3、代码​

function minTaps(n: number, ranges: number[]): number {
    const dp = ranges.map(() => Infinity);

    for (let i = 0, r = 0; i <= n; i++) {
        r = ranges[i];
        if (i - r < 1) dp[i] = 1;

        for (let j = Math.max(0, i - r); j <= Math.min(n, i + r); j++) {
            const di = Math.abs(dp[i]), dj = Math.abs(dp[j]);
            if (j < i && dj + 1 <= di) dp[i] = dj + 1;
            else if (j > i) {
                if (dp[i] > 0 && di <= dj) dp[j] = -di;
                else if (dp[i] <= 0 && di + 1 <= dj) dp[j] = -di - 1;
            }
        }
    }

    return dp.at(-1) < Infinity ? Math.abs(dp.at(-1)) : -1;
};

4、复杂度​

• 时间复杂度：$O(mn)$
• 空间复杂度：$O(n)$

5、执行结果​

1、题干​

给你一个由若干 0 和 1 组成的二维网格 grid，请你找出边界全部由 1 组成的最大 正方形 子网格，并返回该子网格中的元素数量。如果不存在，则返回 0。

示例 1：

输入：grid = [[1,1,1],[1,0,1],[1,1,1]]
输出：9

示例 2：

输入：grid = [[1,1,0,0]]
输出：1

提示：

• 1 <= grid.length <= 100
• 1 <= grid[0].length <= 100
• grid[i][j] 为 0 或 1

2、思路​

纯模拟，毫无技巧，全是感情🤡

遍历网格，以当前网格单元作为正方形左上顶点，先求出左上两条边长的最大可能值，再验证右下两条边是否满足要求。

优化代码又折腾了一番，速度得到一些提升，从最快 88ms 达到最快 68ms。

主要优化在于检查边长的时候，由于是正方形可以同时检查两条边。做法是固定起始位置，然后改变边长，两条边同时满足要求时才往下遍历。

3、代码​

function largest1BorderedSquare(grid: number[][]): number {
    let maxLen = 0;
    const m = grid.length, n = grid[0].length;

    for (let i = 0; i < m - maxLen; i++) {
        for (let j = 0; j < n - maxLen; j++) {
            if (!grid[i][j]) continue;

            let len = 1;
            while (grid[i][j + len] && grid[i + len]?.at(j)) len++;

            for (; len > maxLen; len--) {
                let step = 1, ei = i + len - 1, ej = j + len - 1;
                while (step < len && grid[i + step][ej] && grid[ei][j + step]) step++;

                if (step === len) maxLen = len;
            }
        }
    }

    return maxLen ** 2;
};

下面是最开始的代码，可以对照看看

function largest1BorderedSquare(grid: number[][]): number {
    let maxLen = 0;
    const m = grid.length, n = grid[0].length;

    for (let i = 0; i < m - maxLen; i++) {
        for (let j = 0; j < n - maxLen; j++) {
            if (!grid[i][j]) continue;

            let si = i + 1, sj = j + 1;
            while (si < m && grid[si]?.at(j)) si++;
            while (sj < n && grid[i][sj]) sj++;

            let len = Math.min(si - i, sj - j);
            for (; len > maxLen; len--) {
                let ei = i + len - 1, ej = j + len - 1;
                while (ei > i && grid[ei][j + len - 1]) ei--;
                while (ej > j && grid[i + len - 1][ej]) ej--;

                if (ei === i && ej === j) maxLen = Math.max(maxLen, len);
            }
        }
    }

    return maxLen ** 2;
};

4、复杂度​

• 时间复杂度：最差$O(n^4)$
• 空间复杂度：$O(1)$

5、执行结果​

1、题干​

给你一个整数数组 nums 。你需要选择 恰好 一个下标（下标从 0 开始）并删除对应的元素。请注意剩下元素的下标可能会因为删除操作而发生改变。

比方说，如果 nums = [6,1,7,4,1] ，那么：

• 选择删除下标 1 ，剩下的数组为 nums = [6,7,4,1] 。
• 选择删除下标 2 ，剩下的数组为 nums = [6,1,4,1] 。
• 选择删除下标 4 ，剩下的数组为 nums = [6,1,7,4] 。

如果一个数组满足奇数下标元素的和与偶数下标元素的和相等，该数组就是一个 平衡数组 。

请你返回删除操作后，剩下的数组 nums 是 平衡数组 的 方案数 。

示例 1：

输入：nums = [2,1,6,4]
输出：1
解释：
删除下标 0 ：[1,6,4] -> 偶数元素下标为：1 + 4 = 5 。奇数元素下标为：6 。不平衡。
删除下标 1 ：[2,6,4] -> 偶数元素下标为：2 + 4 = 6 。奇数元素下标为：6 。平衡。
删除下标 2 ：[2,1,4] -> 偶数元素下标为：2 + 4 = 6 。奇数元素下标为：1 。不平衡。
删除下标 3 ：[2,1,6] -> 偶数元素下标为：2 + 6 = 8 。奇数元素下标为：1 。不平衡。
只有一种让剩余数组成为平衡数组的方案。

示例 2：

输入：nums = [1,1,1]
输出：3
解释：你可以删除任意元素，剩余数组都是平衡数组。

示例 3：

输入：nums = [1,2,3]
输出：0
解释：不管删除哪个元素，剩下数组都不是平衡数组。

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 104

2、思路​

前缀和模拟

3、代码​

function waysToMakeFair(nums: number[]): number {
    let oddSum = 0, evenSum = 0;
    const sums = new Array(nums.length).fill(0);
    for (let i = 0; i < nums.length; i++) {
        sums[i] = i % 2 ? oddSum += nums[i] : evenSum += nums[i];
    }

    let ans = 0;
    const oddTail = !!((nums.length - 1) % 2);

    for (let i = 0; i < nums.length; i++) {
        const os1 = (i % 2 ? sums[i] : sums[i - 1]) || 0;
        const es1 = (i % 2 ? sums[i - 1] : sums[i]) || 0;

        const os2 = (sums.at(oddTail ? -2 : -1) || 0) - es1;
        const es2 = (sums.at(oddTail ? -1 : -2) || 0) - os1;

        if (i % 2 === 1 && os1 + os2 - nums[i] === es1 + es2) ans++;
        else if (i % 2 === 0 && os1 + os2 === es1 + es2 - nums[i]) ans++;
    }

    return ans;
};

4、复杂度​

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

5、执行结果​

1、题干​

给你一个 m * n 的矩阵，矩阵中的元素不是 0 就是 1，请你统计并返回其中完全由 1 组成的 正方形 子矩阵的个数。

示例 1：

输入：matrix =
[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]
输出：15
解释： 
边长为 1 的正方形有 10 个。
边长为 2 的正方形有 4 个。
边长为 3 的正方形有 1 个。
正方形的总数 = 10 + 4 + 1 = 15.

示例 2：

输入：matrix = 
[
  [1,0,1],
  [1,1,0],
  [1,1,0]
]
输出：7
解释：
边长为 1 的正方形有 6 个。 
边长为 2 的正方形有 1 个。
正方形的总数 = 6 + 1 = 7.

提示：

• 1 <= arr.length <= 300
• 1 <= arr[0].length <= 300
• 0 <= arr[i][j] <= 1

Problem: 1277. 统计全为 1 的正方形子矩阵

2、方法1​

前缀和+暴力枚举

3、Code​

function countSquares(matrix: number[][]): number {
    const preSum = matrix.map(m => m.map(() => 0));

    for (let i = 0; i < matrix.length; i++) {
        let sumRow = 0;
        for (let j = 0; j < matrix[0].length; j++) {
            sumRow += matrix[i][j];
            preSum[i][j] = sumRow + (i ? preSum[i - 1][j] : 0);
        }
    }

    let ans = 0;

    for (let i = 0; i < matrix.length; i++) {
        for (let j = 0; j < matrix[0].length; j++) {
            for (let k = 1; k <= j + 1; k++) {
                const sr = i - k > -1 ? preSum[i - k][j] : 0;
                const sc = preSum[i][j - k] || 0;
                const src = i - k > -1 && j - k > -1 ? preSum[i - k][j - k] : 0;
                const s = preSum[i][j] - sr - sc + src;
                if (s !== k ** 2) break;
                ans++;
            }
        }
    }

    return ans;
};

4、复杂度​

• 时间复杂度：$O(n^3)$
• 空间复杂度：$O(n^2)$

5、执行结果​

6、方法2​

动态规划

7、Code​

function countSquares(matrix: number[][]): number {
    let ans = 0;

    for (let i = 0; i < matrix.length; i++) {
        for (let j = 0; j < matrix[0].length; j++) {
            if (i && j && matrix[i][j]) matrix[i][j] = Math.min(matrix[i][j - 1], matrix[i - 1][j], matrix[i - 1][j - 1]) + 1;
            ans += matrix[i][j];
        }
    }

    return ans;
};

8、复杂度​

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(1)$

9、执行结果​

1、题干​

你打算做甜点，现在需要购买配料。目前共有 n 种冰激凌基料和 m 种配料可供选购。而制作甜点需要遵循以下几条规则：

• 必须选择 一种 冰激凌基料。
• 可以添加 一种或多种 配料，也可以不添加任何配料。
• 每种类型的配料 最多两份 。

给你以下三个输入：

• baseCosts ，一个长度为 n 的整数数组，其中每个 baseCosts[i] 表示第 i 种冰激凌基料的价格。
• toppingCosts，一个长度为 m 的整数数组，其中每个 toppingCosts[i] 表示 一份 第 i 种冰激凌配料的价格。
• target ，一个整数，表示你制作甜点的目标价格。

你希望自己做的甜点总成本尽可能接近目标价格 target 。

返回最接近 target 的甜点成本。如果有多种方案，返回 成本相对较低 的一种。

示例 1：

输入：baseCosts = [1,7], toppingCosts = [3,4], target = 10
输出：10
解释：考虑下面的方案组合（所有下标均从 0 开始）：
- 选择 1 号基料：成本 7
- 选择 1 份 0 号配料：成本 1 x 3 = 3
- 选择 0 份 1 号配料：成本 0 x 4 = 0
总成本：7 + 3 + 0 = 10 。

示例 2：

输入：baseCosts = [2,3], toppingCosts = [4,5,100], target = 18
输出：17
解释：考虑下面的方案组合（所有下标均从 0 开始）：
- 选择 1 号基料：成本 3
- 选择 1 份 0 号配料：成本 1 x 4 = 4
- 选择 2 份 1 号配料：成本 2 x 5 = 10
- 选择 0 份 2 号配料：成本 0 x 100 = 0
总成本：3 + 4 + 10 + 0 = 17 。不存在总成本为 18 的甜点制作方案。

示例 3：

输入：baseCosts = [3,10], toppingCosts = [2,5], target = 9
输出：8
解释：可以制作总成本为 8 和 10 的甜点。返回 8 ，因为这是成本更低的方案。

示例 4：

输入：baseCosts = [10], toppingCosts = [1], target = 1
输出：10
解释：注意，你可以选择不添加任何配料，但你必须选择一种基料。

提示：

• n == baseCosts.length
• m == toppingCosts.length
• 1 <= n, m <= 10
• 1 <= baseCosts[i], toppingCosts[i] <= 104
• 1 <= target <= 104

Problem: 1774. 最接近目标价格的甜点成本

2、思路​

暴力搜索，确定基料，枚举配料

3、Code​

function closestCost(baseCosts: number[], toppingCosts: number[], target: number): number {
    let ans = baseCosts[0];

    function dfs(c: number, ti: number) {
        if (c === target) return ans = target;
        else {
            const d1 = Math.abs(c - target), d2 = Math.abs(ans - target);
            if (d1 < d2 || (d1 === d2 && c < ans)) ans = c;
        }

        for (let i = ti; i < toppingCosts.length && c <= target; i++) {
            for (let k = 0; k < 3; k++) dfs(c + k * toppingCosts[i], i + 1);
        }
    }

    for (const b of baseCosts) dfs(b, 0);

    return ans;
};

4、执行结果​

1、题干​

有 A 和 B 两种类型 的汤。一开始每种类型的汤有 n 毫升。有四种分配操作：

1. 提供 100ml 的 汤A 和 0ml 的 汤B 。
2. 提供 75ml 的 汤A 和 25ml 的 汤B 。
3. 提供 50ml 的 汤A 和 50ml 的 汤B 。
4. 提供 25ml 的 汤A 和 75ml 的 汤B 。

当我们把汤分配给某人之后，汤就没有了。每个回合，我们将从四种概率同为 0.25 的操作中进行分配选择。如果汤的剩余量不足以完成某次操作，我们将尽可能分配。当两种类型的汤都分配完时，停止操作。

注意 不存在先分配 100 ml 汤B 的操作。

需要返回的值： 汤A 先分配完的概率 +  汤A和汤B 同时分配完的概率 / 2。返回值在正确答案 10-5 的范围内将被认为是正确的。

示例 1:

输入: n = 50
输出: 0.62500
解释:如果我们选择前两个操作，A 首先将变为空。
对于第三个操作，A 和 B 会同时变为空。
对于第四个操作，B 首先将变为空。
所以 A 变为空的总概率加上 A 和 B 同时变为空的概率的一半是 0.25 *(1 + 1 + 0.5 + 0)= 0.625。

示例 2:

输入: n = 100
输出: 0.71875

提示:

• 0 <= n <= 109​​​​​​​

Problem: 808. 分汤

2、思路​

记忆化搜索

3、Code​

function soupServings(n: number): number {
    const operations = [[100, 0], [75, 25], [50, 50], [25, 75]];
    const visited = new Map();

    function serve(ka: number, kb: number) {
        const key = `${ka}-${kb}`;
        if (visited.has(key)) return visited.get(key);

        if (ka <= 0 && kb > 0) return 1;
        else if (ka <= 0 && kb <= 0) return 1 / 2;
        else if (kb <= 0) return 0;

        let r = 0;
        for (const [a, b] of operations) {
            r += 1 / 4 * serve(ka - a, kb - b);
        }

        visited.set(key, r);

        return r;
    }

    return n < 5000 ? serve(n, n) : 1;
};

4、执行结果​