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

1、题干​

给定字符串 s 和字符串数组 words, 返回  words[i] 中是s的子序列的单词个数 。

字符串的 子序列 是从原始字符串中生成的新字符串，可以从中删去一些字符(可以是none)，而不改变其余字符的相对顺序。

• 例如， “ace” 是 “abcde” 的子序列。

示例 1:

输入: s = "abcde", words = ["a","bb","acd","ace"]
输出: 3
解释: 有三个是 s 的子序列的单词: "a", "acd", "ace"。

Example 2:

输入: s = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"]
输出: 2

提示:

• 1 <= s.length <= 5 * 104
• 1 <= words.length <= 5000
• 1 <= words[i].length <= 50
• words[i]和s 都只由小写字母组成。

Problem: 792. 匹配子序列的单词数

2、思路​

二分查找

• 按字母表顺序把字符串 s 中所有字符的下标升序存入二维数组 idxMatrix
• 判断数组 words 中任意字符串 w 是否 s 的子序列，只需要判断 w 中任意字符 c 比前一个字符 在 s 中的下标更大。其中查找 c 在 s 中的下标时，使用二分查找算法

3、Code​

function numMatchingSubseq(s: string, words: string[]): number {
    const CA = 'a'.charCodeAt(0), idxMatrix = new Array(26).fill(0).map(() => []);

    for (let i = 0; i < s.length; i++) {
        const ci = s[i].charCodeAt(0) - CA;
        idxMatrix[ci].push(i);
    }

    function find(nums: number[] = [], k: number) {
        let l = 0, r = nums.length - 1;

        while (l <= r) {
            const m = ((l + r) / 2) >> 0;
            if (nums[m] > k) {
                if (nums[m - 1] > k) r = m - 1;
                else return nums[m];
            } else {
                l = m + 1;
            }
        }

        return -1;
    }

    let res = 0;
    loop: for (const w of words) {
        let preIdx = -1;
        for (const c of w) {
            const ci = c.charCodeAt(0) - CA;
            const ni = find(idxMatrix[ci], preIdx);
            if (ni < 0) continue loop;
            preIdx = ni;
        }
        res++;
    }

    return res;
};

4、复杂度​

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

5、执行结果​

1、题干​

有两种形状的瓷砖：一种是 2 x 1 的多米诺形，另一种是形如 "L" 的托米诺形。两种形状都可以旋转。

给定整数 n ，返回可以平铺 2 x n 的面板的方法的数量。返回对 109 + 7 取模 的值。

平铺指的是每个正方形都必须有瓷砖覆盖。两个平铺不同，当且仅当面板上有四个方向上的相邻单元中的两个，使得恰好有一个平铺有一个瓷砖占据两个正方形。

示例 1:

输入: n = 3
输出: 5
解释: 五种不同的方法如上所示。

示例 2:

输入: n = 1
输出: 1

提示：

• 1 <= n <= 1000

Problem: 790. 多米诺和托米诺平铺

2、思路​

动态规划，挺难想到

• 列的状态有4个：无/上/下/满
• 状态转移也有4个：
  • dp[i][0] = dp[i-1][3]
  • dp[i][1] = dp[i-1][0] + dp[i-1][2]
  • dp[i][2] = dp[i-1][0] + dp[i-1][1]
  • dp[i][3] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2] + dp[i-1][3]

3、Code​

function numTilings(n: number): number {
    // 无/上/下/满
    let M = 1e9 + 7, dp = [1, 0, 0, 1];

    for (let i = 2; i <= n; i++) {
        const d0 = dp[3];
        const d1 = (dp[0] + dp[2]) % M;
        const d2 = (dp[0] + dp[1]) % M;
        const d3 = (dp[0] + dp[1] + dp[2] + dp[3]) % M;
        dp = [d0, d1, d2, d3];
    }

    return dp[3];
};

4、复杂度​

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

5、执行结果​

1、题干​

在一个 n x n 的矩阵 grid 中，除了在数组 mines 中给出的元素为 0，其他每个元素都为 1。mines[i] = [xi, yi]表示 grid[xi][yi] == 0

返回  grid 中包含 1 的最大的 轴对齐 加号标志的阶数 。如果未找到加号标志，则返回 0 。

一个 k 阶由 1 组成的 “轴对称”加号标志 具有中心网格 grid[r][c] == 1 ，以及4个从中心向上、向下、向左、向右延伸，长度为 k-1，由 1 组成的臂。注意，只有加号标志的所有网格要求为 1 ，别的网格可能为 0 也可能为 1 。

示例 1：

输入: n = 5, mines = [[4, 2]]
输出: 2
解释: 在上面的网格中，最大加号标志的阶只能是2。一个标志已在图中标出。

示例 2：

输入: n = 1, mines = [[0, 0]]
输出: 0
解释: 没有加号标志，返回 0 。

提示：

• 1 <= n <= 500
• 1 <= mines.length <= 5000
• 0 <= xi, yi < n
• 每一对 (xi, yi) 都 不重复​​​​​​​

Problem: 764. 最大加号标志

2、思路​

• 暴力：遍历矩阵 grid，把每个网格当成中心，计算加号标志的最大阶数 k
• 哈希：把 0 网格的坐标转换成哈希表降低查找时间复杂度
• 剪枝：遍历过程中，通过当前求得的最大阶数 k 进一步缩小遍历范围

3、Code​

function orderOfLargestPlusSign(n: number, mines: number[][]): number {
    const M = 10007, hash = (x: number, y: number) => x * M + y;
    const set = new Set(mines.map(([x, y]) => hash(x, y)));
    
    let k = 0;
    for (let i = 0; i < n - k; i++) {
        for (let j = k; i >= k && j < n - k; j++) {
            for (let l = 0; l < n / 2; l++) {
                if (i < l || j < l || i + l >= n || j + l >= n) break;
                if (set.has(hash(i, j + l)) || set.has(hash(i, j - l)) || set.has(hash(i + l, j)) || set.has(hash(i - l, j))) break;
                k = Math.max(k, l + 1);
            }
        }
    }

    return k;
}

4、复杂度​

• 时间复杂度：$O(n^3)$
• 空间复杂度：$O(m)$，$m=mines.length$

5、执行结果​

1、题干​

给定一个整数数组 arr，找到 min(b) 的总和，其中 b 的范围为 arr 的每个（连续）子数组。

由于答案可能很大，因此 返回答案模 10^9 + 7 。

示例 1：

输入：arr = [3,1,2,4]
输出：17
解释：
子数组为 [3]，[1]，[2]，[4]，[3,1]，[1,2]，[2,4]，[3,1,2]，[1,2,4]，[3,1,2,4]。 
最小值为 3，1，2，4，1，1，2，1，1，1，和为 17。

示例 2：

输入：arr = [11,81,94,43,3]
输出：444

提示：

• 1 <= arr.length <= 3 * 104
• 1 <= arr[i] <= 3 * 104

解题思路​

单调栈，写得有点费力

代码​

function sumSubarrayMins(arr: number[]): number {
  let res = 0;

  function dfs(c: number) {
    const n = arr[c];
    let [mins, preSum] = c < arr.length - 1 ? dfs(c + 1) : [[], 0];

    let count = 1;
    while (mins.at(-1)?.at(0) >= n) {
      const pair = mins.pop();
      count += pair[1];
      preSum -= pair[1] * pair[0];
    }

    mins.push([n, count]);
    preSum = (preSum + n * count) % (1e9 + 7);
    res = (res + preSum) % (1e9 + 7);

    return [mins, preSum];
  }

  dfs(0);

  return res;
}

1、题干​

现有一个记作二维矩阵 frame 的珠宝架，其中 frame[i][j] 为该位置珠宝的价值。拿取珠宝的规则为：

• 只能从架子的左上角开始拿珠宝
• 每次可以移动到右侧或下侧的相邻位置
• 到达珠宝架子的右下角时，停止拿取

注意：珠宝的价值都是大于 0 的。除非这个架子上没有任何珠宝，比如 frame = [[0]]。

示例 1:

输入: frame = [[1,3,1],[1,5,1],[4,2,1]]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最高价值的珠宝

提示：

• 0 < frame.length <= 200
• 0 < frame[0].length <= 200

2、解法1-动态规划​

循环遍历矩阵，累加礼物价值

状态转移方程：$dp[i][j] += max(dp[i-1][j], dp[i][j-1])$

3、代码​

function maxValue(grid: number[][]): number {
    const m = grid.length, n = grid[0].length;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            grid[i][j] += Math.max(i > 0 ? grid[i - 1][j] : 0, j > 0 ? grid[i][j - 1] : 0);
        }
    }
    return grid[m - 1][n - 1];
};

4、执行结果​

5、解法2-记忆化DFS​

DFS遍历矩阵，累加礼物价值

记录每个节点的最大价值作为缓存避免重复计算

6、代码​

function maxValue(grid: number[][]): number {
    const m = grid.length, n = grid[0].length;
    const visited = grid.map(row => row.map(() => 0));
    function dfs(i: number, j: number) {
        if (i < 0 || j < 0 || i >= m || j >= n) return 0;
        if (!visited[i][j]) visited[i][j] = grid[i][j] + Math.max(dfs(i - 1, j), dfs(i, j - 1));
        return visited[i][j];
    }
    return dfs(m - 1, n - 1);
};

7、执行结果​

• 执行用时: 56 ms
• 内存消耗: 44.1 MB

1、题干​

在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

示例 1:

输入: 
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物

提示：

• 0 < grid.length <= 200
• 0 < grid[0].length <= 200

2、解法1-动态规划​

循环遍历矩阵，累加礼物价值

状态转移方程：$dp[i][j] += max(dp[i-1][j], dp[i][j-1])$

3、代码​

function maxValue(grid: number[][]): number {
    const m = grid.length, n = grid[0].length;
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            grid[i][j] += Math.max(i > 0 ? grid[i - 1][j] : 0, j > 0 ? grid[i][j - 1] : 0);
        }
    }
    return grid[m - 1][n - 1];
};

4、执行结果​

5、解法2-记忆化DFS​

DFS遍历矩阵，累加礼物价值

记录每个节点的最大价值作为缓存避免重复计算

6、代码​

function maxValue(grid: number[][]): number {
    const m = grid.length, n = grid[0].length;
    const visited = grid.map(row => row.map(() => 0));
    function dfs(i: number, j: number) {
        if (i < 0 || j < 0 || i >= m || j >= n) return 0;
        if (!visited[i][j]) visited[i][j] = grid[i][j] + Math.max(dfs(i - 1, j), dfs(i, j - 1));
        return visited[i][j];
    }
    return dfs(m - 1, n - 1);
};

7、执行结果​

• 执行用时: 56 ms
• 内存消耗: 44.1 MB

1、题干​

给定一正整数数组 nums，nums 中的相邻整数将进行浮点除法。例如， [2,3,4] -> 2 / 3 / 4 。

• 例如，nums = [2,3,4]，我们将求表达式的值 "2/3/4"。

但是，你可以在任意位置添加任意数目的括号，来改变算数的优先级。你需要找出怎么添加括号，以便计算后的表达式的值为最大值。

以字符串格式返回具有最大值的对应表达式。

注意：你的表达式不应该包含多余的括号。

示例 1：

输入: [1000,100,10,2]
输出: "1000/(100/10/2)"
解释: 1000/(100/10/2) = 1000/((100/10)/2) = 200
但是，以下加粗的括号 "1000/((100/10)/2)" 是冗余的，
因为他们并不影响操作的优先级，所以你需要返回 "1000/(100/10/2)"。

其他用例:
1000/(100/10)/2 = 50
1000/(100/(10/2)) = 50
1000/100/10/2 = 0.5
1000/100/(10/2) = 2

示例 2:

输入: nums = [2,3,4]
输出: "2/(3/4)"
解释: (2/(3/4)) = 8/3 = 2.667
可以看出，在尝试了所有的可能性之后，我们无法得到一个结果大于 2.667 的表达式。

说明:

• 1 <= nums.length <= 10
• 2 <= nums[i] <= 1000
• 对于给定的输入只有一种最优除法。

2、解题思路​

贪心，加括号使得被除数最大、除数最小即可

3、代码​

var optimalDivision = function (nums) {
    return nums.length < 3 ? nums.join('/') : `${nums.shift()}/(${nums.join('/')})`;
};

4、执行结果​

1、题干​

用一个大小为 m x n 的二维网格 grid 表示一个箱子。你有 n 颗球。箱子的顶部和底部都是开着的。

箱子中的每个单元格都有一个对角线挡板，跨过单元格的两个角，可以将球导向左侧或者右侧。

• 将球导向右侧的挡板跨过左上角和右下角，在网格中用 1 表示。
• 将球导向左侧的挡板跨过右上角和左下角，在网格中用 -1 表示。

在箱子每一列的顶端各放一颗球。每颗球都可能卡在箱子里或从底部掉出来。如果球恰好卡在两块挡板之间的 "V" 形图案，或者被一块挡导向到箱子的任意一侧边上，就会卡住。

返回一个大小为 n 的数组 answer ，其中 answer[i] 是球放在顶部的第 i 列后从底部掉出来的那一列对应的下标，如果球卡在盒子里，则返回 -1 。

示例 1：

输入：grid = [[1,1,1,-1,-1],[1,1,1,-1,-1],[-1,-1,-1,1,1],[1,1,1,1,-1],[-1,-1,-1,-1,-1]]
输出：[1,-1,-1,-1,-1]
解释：示例如图：
b0 球开始放在第 0 列上，最终从箱子底部第 1 列掉出。
b1 球开始放在第 1 列上，会卡在第 2、3 列和第 1 行之间的 "V" 形里。
b2 球开始放在第 2 列上，会卡在第 2、3 列和第 0 行之间的 "V" 形里。
b3 球开始放在第 3 列上，会卡在第 2、3 列和第 0 行之间的 "V" 形里。
b4 球开始放在第 4 列上，会卡在第 2、3 列和第 1 行之间的 "V" 形里。

示例 2：

输入：grid = [[-1]]
输出：[-1]
解释：球被卡在箱子左侧边上。

示例 3：

输入：grid = [[1,1,1,1,1,1],[-1,-1,-1,-1,-1,-1],[1,1,1,1,1,1],[-1,-1,-1,-1,-1,-1]]
输出：[0,1,2,3,4,-1]

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 100
• grid[i][j] 为 1 或 -1

2、解题思路​

按题意模拟

3、代码​

var findBall = function (grid) {
    const res = [], m = grid.length, n = grid[0].length;

    for (let j = 0; j < n; j++) {
        let k = j;
        for (let i = 0; i < m; i++) {
            if (grid[i][k] === 1 && grid[i][k] === grid[i][k + 1]) k++;
            else if (grid[i][k] === -1 && grid[i][k] === grid[i][k - 1]) k--;
            else res[j] = -1;
        }
        if (res[j] === undefined) res[j] = k;
    }

    return res;
};

4、执行结果​

1、题干​

给你一个整数数组 nums 。如果 nums 的一个子集中，所有元素的乘积可以表示为一个或多个 互不相同的质数 的乘积，那么我们称它为 好子集 。

• 比方说，如果 nums = [1, 2, 3, 4] ：
  • [2, 3] ，[1, 2, 3] 和 [1, 3] 是 好 子集，乘积分别为 6 = 2*3 ，6 = 2*3 和 3 = 3 。
  • [1, 4] 和 [4] 不是 好 子集，因为乘积分别为 4 = 2*2 和 4 = 2*2 。

请你返回 nums 中不同的 好 子集的数目对 109 + 7 取余 的结果。

nums 中的 子集 是通过删除 nums 中一些（可能一个都不删除，也可能全部都删除）元素后剩余元素组成的数组。如果两个子集删除的下标不同，那么它们被视为不同的子集。

示例 1：

输入：nums = [1,2,3,4]
输出：6
解释：好子集为：
- [1,2]：乘积为 2 ，可以表示为质数 2 的乘积。
- [1,2,3]：乘积为 6 ，可以表示为互不相同的质数 2 和 3 的乘积。
- [1,3]：乘积为 3 ，可以表示为质数 3 的乘积。
- [2]：乘积为 2 ，可以表示为质数 2 的乘积。
- [2,3]：乘积为 6 ，可以表示为互不相同的质数 2 和 3 的乘积。
- [3]：乘积为 3 ，可以表示为质数 3 的乘积。

示例 2：

输入：nums = [4,2,3,15]
输出：5
解释：好子集为：
- [2]：乘积为 2 ，可以表示为质数 2 的乘积。
- [2,3]：乘积为 6 ，可以表示为互不相同质数 2 和 3 的乘积。
- [2,15]：乘积为 30 ，可以表示为互不相同质数 2，3 和 5 的乘积。
- [3]：乘积为 3 ，可以表示为质数 3 的乘积。
- [15]：乘积为 15 ，可以表示为互不相同质数 3 和 5 的乘积。

提示：

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

2、解题思路​

• 状态压缩：对数组 nums 使用哈希表计数，所有的键都会集中在 $[1,30]$ 这个区间
• 从哈希表中剔除存在多个相同因子的数，比如4,8,12
• 使用 BFS 思路对符合要求的数字进行好子集组合，第一层为1个数的组合，第二层为2个数的组合，以此类推
• 组合过程中记得剔除掉存在最大公约数不为1的情况，另外注意去重
• 计算每层好子集数量并累加
  • 好子集数量等于子集各元素个数相乘
  • 若子集中存在 $1$，不是乘以 $1$ 的数量 $c1$，而应该乘以 $1$ 的组合总数 $2^{c1}-1$，由于 $c1$ 可能很大直接计算会溢出，可以使用累乘并模 $1e9+7$

这道题最大的坑在于对数字 $1$ 的特殊处理，这个解法和代码都不是最优的，抽空再优化了

3、代码​

var numberOfGoodSubsets = function (nums) {
    const MOD = 1e9 + 7;
    const nMap = nums.reduce((a, c) => a.set(c, (a.get(c) || 0) + 1), new Map());
    const bNums = [4, 9, 16, 25, 8, 27, 16];
    const gNums = [...nMap.keys()].filter(n => bNums.every((b) => n % b)).sort((a, b) => a - b);
    const gcd = (a, b) => (b ? gcd(b, a % b) : a);

    let cn1 = 1;
    for (let c1 = nMap.get(1); c1; c1--) cn1 = 2 * cn1 % MOD;

    let count = 0, queue = gNums.map((n) => [n]);
    while (queue.length) {
        const nextQueue = [];
        for (const arr of queue) {
            for (const g of gNums) {
                if (g <= arr[arr.length - 1] || arr.some((a) => gcd(a, g) > 1)) continue;
                nextQueue.push([...arr, g]);
            }

            if (arr.length === 1 && arr[0] === 1) continue;
            count += arr.reduce((a, c) => {
                const cn = c > 1 ? nMap.get(c) : cn1 - 1;
                return a * cn % MOD;
            }, 1);
            count = count % MOD;
        }
        queue = nextQueue;
    }

    return count;
};

4、执行结果​

• 执行用时: 468 ms
• 内存消耗: 63.9 MB

1、题干​

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

输入：n = 1
输出：["()"]

提示：

• 1 <= n <= 8

2、解题思路​

总体思路是：从 n-1 推导出 n 的组合情况，只需要遍历 n-1 的所有组合，并在所有组合的每个位置填入一对括号 () 并去重即可。

3、举个例子​

• n=1时，组合情况仅一种：["()"]
• n=2时
  • 遍历 n=1 的组合情况 ["()"]
  • 对于情况 "()"，在该字符串每个位置填入一对括号 () 后得到：["()()","(())","()()"]
  • 去重得到最终组合情况为：["()()","(())"]
• n=3时
  • 遍历 n=2 的组合情况 ["()()","(())"]
  • 对于情况 "()()"，在每个位置填入一对括号 () 后得到：["()()()","(())()","()()()","()(())","()()()"]
  • 对于情况 "(())"，在每个位置填入一对括号 () 后得到：["()(())","(()())","((()))","(()())","(())()"]
  • 去重得到最终组合情况为：["()()()","(())()","()(())","(()())","((()))"]

4、代码​

var generateParenthesis = function (n) {
    let set = new Set(['()']);
    for (let c = 2; c <= n; c++) {
        let nextSet = new Set();
        for (const s of set) {
            for (let j = 0; j <= s.length; j++) {
                nextSet.add(s.slice(0, j) + '()' + s.slice(j));
            }
        }
        set = nextSet;
    }
    return [...set];
};

5、执行结果​