动态规划 – 第 5 页

目标

在一个 n x n 的国际象棋棋盘上，一个骑士从单元格 (row, column) 开始，并尝试进行 k 次移动。行和列是从 0 开始的，所以左上单元格是 (0,0) ，右下单元格是 (n - 1, n - 1) 。

象棋骑士有8种可能的走法，如下图所示。每次移动在基本方向上是两个单元格，然后在正交方向上是一个单元格。

每次骑士要移动时，它都会随机从8种可能的移动中选择一种(即使棋子会离开棋盘)，然后移动到那里。

骑士继续移动，直到它走了 k 步或离开了棋盘。

返回骑士在棋盘停止移动后仍留在棋盘上的概率。

示例 1：

输入: n = 3, k = 2, row = 0, column = 0
输出: 0.0625
解释: 有两步(到(1,2)，(2,1))可以让骑士留在棋盘上。
在每一个位置上，也有两种移动可以让骑士留在棋盘上。
骑士留在棋盘上的总概率是0.0625。

示例 2：

输入: n = 1, k = 0, row = 0, column = 0
输出: 1.00000

说明:

1 <= n <= 25
0 <= k <= 100
0 <= row, column <= n - 1

思路

在 n x n 棋盘上的 (row, column) 位置上有一个骑士（坐标从 0 开始），求它朝 8 个方向任意走 k 次还停留在棋盘上的概率是多少。所谓的 8 个方向类似中国象棋中的马走 日，不过没有蹩马腿的限制。

定义 dp[i][j][k] 表示当前在 (i, j) 走 k 步后最终在棋盘上的概率。初始 dp[i][j][0] = 1，dp[i][j][k] = Σdp[.][.][k - 1] / 8，最终的结果为 dp[row][column][k]。

代码


/**
 * @date 2024-12-07 20:48
 */
public class KnightProbability688 {

    public double knightProbability(int n, int k, int row, int column) {
        int[][] direction = new int[][]{{-1, -2}, {-2, -1}, {-1, 2}, {-2, 1}, {1, 2}, {2, 1}, {1, -2}, {2, -1}};
        double[][][] dp = new double[n][n][k + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j][0] = 1.0;
            }
        }
        for (int step = 1; step <= k; step++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    for (int d = 0; d < 8; d++) {
                        int dx = direction[d][0];
                        int dy = direction[d][1];
                        int x = i + dx;
                        int y = j + dy;
                        if (x >= 0 && x < n && y >= 0 && y < n) {
                            dp[i][j][step] += dp[x][y][step - 1];
                        }
                    }
                    dp[i][j][step] /= 8;
                }
            }
        }
        return dp[row][column][k];
    }

}

性能

目标

给你一个长度为 n 的正整数数组 nums 。

如果两个非负整数数组 (arr1, arr2) 满足以下条件，我们称它们是单调数组对：

两个数组的长度都是 n 。
arr1 是单调非递减的，换句话说 arr1[0] <= arr1[1] <= ... <= arr1[n - 1] 。
arr2 是单调非递增的，换句话说 arr2[0] >= arr2[1] >= ... >= arr2[n - 1] 。
对于所有的 0 <= i <= n - 1 都有 arr1[i] + arr2[i] == nums[i] 。

请你返回所有单调数组对的数目。

由于答案可能很大，请你将它对 109 + 7 取余后返回。

示例 1：

输入：nums = [2,3,2]
输出：4
解释：
单调数组对包括：
([0, 1, 1], [2, 2, 1])
([0, 1, 2], [2, 2, 0])
([0, 2, 2], [2, 1, 0])
([1, 2, 2], [1, 1, 0])

示例 2：

输入：nums = [5,5,5,5]
输出：126

说明：

1 <= n == nums.length <= 2000
1 <= nums[i] <= 1000

思路

有一个长度为 n 正整数数组 nums，可以将其拆成两个数组 arr1 arr2，使之满足 arr1[i] + arr2[i] == nums[i]。问有多少种拆分方法使得 arr1 非递减且 arr2 非递增。

与昨天的 3250.单调数组对的数目I 相比，nums[i] 的最大值从 50 变成了 1000。时间复杂度大概为 O(n*m^2)，m 为 nums[i] 的最大值，如果还沿用昨天的解法就会超时。

先将昨天的题目改写为动态规划，定义 dp[i][j] 表示最后一个元素为 j，长度为 i + 1 的满足条件的 arr1 个数。由于 arr1 是非递减的，如果最后一个元素为 arr1[i] = j 那么倒数第二个元素arr1[i - 1] <= j。同时我们还要考虑到 arr2 非递增，即 arr2[i - 1] >= arr2[i]，nums[i - 1] - arr1[i - 1] >= nums[i] - arr1[i]，arr1[i - 1] <= nums[i - 1] - nums[i] + arr1[i]。综上，arr1[i - 1] <= Math.min(j, nums[i - 1] - nums[i] + j)。

经过上面的分析，dp[i][j] = Σdp[i - 1][k]，其中 k ∈ [0, Math.min(j, nums[i - 1] - nums[i] + j)]。这样写会超时，针对每个 j，我们会进行多次重复的计算。

令 d = nums[i - 1] - nums[i]，当 d >= 0 时，上界为 j，否则上界为 j + d。

考虑 nums[i - 1] < nums[i]，即 d < 0：

当 arr1[i - 1] = j 时，令arr2[i - 1] = nums[i - 1] - j = a
当 arr1[i] = j 时，arr2[i] = nums[i] - arr1[i] = nums[i - 1] - d - j = a - d，d < 0。

也就是说，当 arr1[i] 的取值与上一层一样时，arr2[i] 比上一层的值大了 |d|。为了使第 i 层 arr2 非递增，那么 arr1 的取值只能从 |d| 开始。

它们之间的约束关系是这样的，当 nums[i] 变大，arr1 第 i 层取 j 时，arr2 的第 i 层比上一层增大了 |d|，这时我们必须舍弃 [0, |d|) 的取值，因为它必定大于上一层 arr2 的最大值。然后考虑第 i 层的 arr1 取 [|d|, nums[i]] 的情况，由于第 i 层的 arr2 相比第 i - 1 层增大了 |d|，因此需要减小第 i - 1 层的 arr1，使第 i - 1 层的 arr2 增大。所以第 i 层的 j 对应第 i - 1 层的 j - |d|。

dp[i][j] 的取值类似前缀和，只不过有约束条件，并不是所有值都合法。考虑简单的情况 nums[0] == nums[1] && i == 1，

当 j == 0 时，dp[1][0] = dp[0][0] = 1
当 j == 1 时，上一层（i == 0） arr1 可以取 0、1，dp[1][1] = dp[1][0] + dp[0][1] = 2
当 j == 2 时，上一层（i == 0） arr1 可以取 0、1、2，dp[1][2] = dp[1][1] + dp[0][2] = 3

因此我们有 dp[i][j] = (dp[i][j - 1] + dp[i - 1][j - d])。

代码


/**
 * @date 2024-11-29 9:39
 */
public class CountOfPairs3251 {

    public static int MOD = 1000000007;

    public int countOfPairs(int[] nums) {
        int res = 0;
        int n = nums.length;
        int[][] dp = new int[n][1001];
        for (int i = 0; i <= nums[0]; i++) {
            dp[0][i] = 1;
        }
        for (int i = 1; i < n; i++) {
            int d = Math.max(nums[i] - nums[i - 1], 0);
            for (int j = d; j <= nums[i]; j++) {
                if (j == 0) {
                    dp[i][j] = dp[i - 1][0] % MOD;
                } else {
                    dp[i][j] = (dp[i][j - 1] + dp[i - 1][j - d]) % MOD;
                }
            }
        }
        for (int i : dp[n - 1]) {
            res = (res + i) % MOD;
        }
        return res;
    }

}

性能

3250.单调数组对的数目I

目标

给你一个长度为 n 的正整数数组 nums 。

如果两个非负整数数组 (arr1, arr2) 满足以下条件，我们称它们是单调数组对：

两个数组的长度都是 n 。
arr1 是单调非递减的，换句话说 arr1[0] <= arr1[1] <= ... <= arr1[n - 1] 。
arr2 是单调非递增的，换句话说 arr2[0] >= arr2[1] >= ... >= arr2[n - 1] 。
对于所有的 0 <= i <= n - 1 都有 arr1[i] + arr2[i] == nums[i] 。

请你返回所有单调数组对的数目。

由于答案可能很大，请你将它对 10^9 + 7 取余后返回。

示例 1：

输入：nums = [2,3,2]
输出：4
解释：
单调数组对包括：
([0, 1, 1], [2, 2, 1])
([0, 1, 2], [2, 2, 0])
([0, 2, 2], [2, 1, 0])
([1, 2, 2], [1, 1, 0])

示例 2：

输入：nums = [5,5,5,5]
输出：126

说明：

1 <= n == nums.length <= 2000
1 <= nums[i] <= 50

提示：

Let dp[i][s] is the number of monotonic pairs of length i with the arr1[i - 1] = s.
If arr1[i - 1] = s, arr2[i - 1] = nums[i - 1] - s.
Check if the state in recurrence is valid.

思路

有一个长度为 n 的正整数数组 nums，可以将其拆成两个数组 arr1 arr2，使之满足 arr1[i] + arr2[i] == nums[i]。问有多少种拆分方法使得 arr1 非递减且 arr2 非递增。

显然 arr1 确定之后，arr2 也就确定了。考虑枚举 arr1，判断 arr1 是否非递减，以及arr2 是否非递增。可以使用记忆化搜索，对于位置 i，arr1 与 arr2 需要满足下面的条件：

arr1[i] >= arr1[i - 1]
arr2[i] = nums[i] - arr1[i] <= arr2[i - 1] = nums[i - 1] - arr1[i - 1]，即 arr1[i] >= nums[i] - nums[i - 1] + arr1[i - 1]

也就是 nums[i] >= arr1[i] >= Math.max(nums[i] - nums[i - 1] + arr1[i - 1], arr1[i - 1])。

代码


/**
 * @date 2024-11-28 10:36
 */
public class CountOfPairs3250 {

    public static int MOD = 1000000007;

    public int countOfPairs(int[] nums) {
        int res = 0;
        int n = nums.length;
        int[][] mem = new int[n + 1][51];
        for (int[] arr : mem) {
            Arrays.fill(arr, -1);
        }
        for (int i = 0; i <= nums[0]; i++) {
            res = (res + dfs(nums, 1, i, mem)) % MOD;
        }
        return res;
    }

    public int dfs(int[] nums, int i, int prev, int[][] mem) {
        int n = nums.length;
        if (i == n) {
            return 1;
        }
        int lowerBound = Math.max(prev, nums[i] - nums[i - 1] + prev);
        int next = i + 1;
        int res = 0;
        for (int j = lowerBound; j <= nums[i]; j++) {
            if (mem[next][j] == -1) {
                mem[next][j] = dfs(nums, next, j, mem) % MOD;
            }
            res = (res + mem[next][j]) % MOD;
        }
        return res;
    }

}

性能

743.网络延迟时间

目标

有 n 个网络节点，标记为 1 到 n。

给你一个列表 times，表示信号经过有向边的传递时间。 times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。

现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。

示例 1：

输入：times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
输出：2

示例 2：

输入：times = [[1,2,1]], n = 2, k = 1
输出：1

示例 3：

输入：times = [[1,2,1]], n = 2, k = 2
输出：-1

说明：

1 <= k <= n <= 100
1 <= times.length <= 6000
times[i].length == 3
1 <= ui, vi <= n
ui != vi
0 <= wi <= 100
所有 (ui, vi) 对都互不相同（即，不含重复边）

思路

有一个 n 个节点的有向图，节点标记为 1 ~ n，求从其中某个节点 k 出发访问到所有其它节点的最短时间。

即从 k 出发求出到达所有其它节点的最短路径，然后取其中的最大值。

Floyd 算法的基本思想是动态规划。定义 dp[i][j] 表示从节点 i 到节点 j 的最短路径，对于所有其它中间节点 m，更新 dp[i][j] = Math.min(dp[i][j], dp[i][m] + dp[m][j])，时间复杂度 O(n^3)。

如果 i -> j 有直接的通路则初始化 dp[i][j] 为路径的权值，否则为 INF。

但是本题不需要其它起点的最短路径，因此可以使用 Dijkstra 算法、Bellman-Ford 算法或者 SPFA 算法。

图的表示可以使用邻接矩阵、邻接表、前向星、链式前向星等结构。

代码


/**
 * @date 2024-11-25 9:08
 */
public class NetworkDelayTime743 {

    public int networkDelayTime(int[][] times, int n, int k) {
        int[][] dp = new int[n + 1][n + 1];
        for (int[] cost : dp) {
            Arrays.fill(cost, 20000);
        }
        for (int[] edge : times) {
            dp[edge[0]][edge[1]] = edge[2];
        }
        for (int m = 1; m <= n; m++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (i == j || i == m || j == m) {
                        continue;
                    }
                    dp[i][j] = Math.min(dp[i][j], dp[i][m] + dp[m][j]);
                }
            }
        }
        int res = -1;
        for (int i = 1; i <= n; i++) {
            if (i == k) {
                continue;
            }
            res = Math.max(dp[k][i], res);
        }
        return res == 20000 ? -1 : res;
    }

}

性能

3243.新增道路查询后的最短距离I

目标

给你一个整数 n 和一个二维整数数组 queries。

有 n 个城市，编号从 0 到 n - 1。初始时，每个城市 i 都有一条单向道路通往城市 i + 1（ 0 <= i < n - 1）。

queries[i] = [ui, vi] 表示新建一条从城市 ui 到城市 vi 的单向道路。每次查询后，你需要找到从城市 0 到城市 n - 1 的最短路径的长度。

返回一个数组 answer，对于范围 [0, queries.length - 1] 中的每个 i，answer[i] 是处理完前 i + 1 个查询后，从城市 0 到城市 n - 1 的最短路径的长度。

示例 1：

输入： n = 5, queries = [[2, 4], [0, 2], [0, 4]]
输出： [3, 2, 1]
解释：
新增一条从 2 到 4 的道路后，从 0 到 4 的最短路径长度为 3。
新增一条从 0 到 2 的道路后，从 0 到 4 的最短路径长度为 2。
新增一条从 0 到 4 的道路后，从 0 到 4 的最短路径长度为 1。

示例 2：

输入： n = 4, queries = [[0, 3], [0, 2]]
输出： [1, 1]
解释：
新增一条从 0 到 3 的道路后，从 0 到 3 的最短路径长度为 1。
新增一条从 0 到 2 的道路后，从 0 到 3 的最短路径长度仍为 1。

说明：

3 <= n <= 500
1 <= queries.length <= 500
queries[i].length == 2
0 <= queries[i][0] < queries[i][1] < n
1 < queries[i][1] - queries[i][0]
查询中没有重复的道路。

思路

有 n 个城市，刚开始每一个城市 i 有一条单项道路通向城市 i + 1，有一个二维数组 queries，queries[i] 表示增加一条从 queries[i][0] 到 queries[i][1] 的单项道路，返回 answer 数组，answer[i] 表示增加了 queries[i] 之后从城市 0 到城市 n - 1 的最短路径。

建图，每次增加路径之后使用BFS计算最短路径。注意过滤重复元素，否则过不了。

也可以使用动态规划来做。

定义 dp[i] 表示从城市 i 到城市 n - 1 的最短路径，每添加一条路径，受影响的只有包括起点在内前面的城市。当增加一条道路 [l, r]，状态转移方程为 dp[l] = Math.min(dp[r] + 1, dp[l])，表示从 r 到达终点加一步与原来值的最小值。我们需要同步更新 l 之前的 dp 值。我们可以倒序遍历 [0, l)，dp[j] = Math.min(dp[j], dp[j + 1] + 1) 取其自身与后面元素 dp 值加一的较小值，同时还要考虑区间内有前面查询新增的道路，比如前面有以 j 为起点的查询，还要再取一个较小值 Math.min(dp[j], dp[end] + 1)，end 表示之前增加的道路的终点。

代码


/**
 * @date 2024-11-19 0:47
 */
public class ShortestDistanceAfterQueries3243 {

    public int[] shortestDistanceAfterQueries_v2(int n, int[][] queries) {
        int[] dp = new int[n];
        int ql = queries.length;
        int[] res = new int[ql];
        for (int i = 0; i < n; i++) {
            dp[i] = n - i - 1;
        }
        Map<Integer, List<Integer>> map = new HashMap<>(ql);
        for (int i = 0; i < ql; i++) {
            int l = queries[i][0];
            int r = queries[i][1];
            dp[l] = Math.min(dp[r] + 1, dp[l]);
            for (int j = l - 1; j >= 0; j--) {
                dp[j] = Math.min(dp[j], dp[j + 1] + 1);
                if (map.containsKey(j)) {
                    for (Integer end : map.get(j)) {
                        dp[j] = Math.min(dp[j], dp[end] + 1);
                    }
                }
            }
            res[i] = dp[0];
            map.putIfAbsent(l, new ArrayList<>());
            map.get(l).add(r);
        }
        return res;
    }

    public int[] shortestDistanceAfterQueries_v1(int n, int[][] queries) {
        List<Integer>[] g = new ArrayList[n];
        for (int i = 0; i < g.length; i++) {
            g[i] = new ArrayList<>();
            g[i].add(i + 1);
        }
        int ql = queries.length;
        int[] res = new int[ql];
        for (int i = 0; i < ql; i++) {
            g[queries[i][0]].add(queries[i][1]);
            res[i] = bfs_v1(g);
        }
        return res;
    }

    public int bfs_v1(List<Integer>[] g) {
        int n = g.length;
        List<Integer> list = new ArrayList<>();
        boolean[] visited = new boolean[n];
        list.add(0);
        for (int res = 1; ; res++) {
            List<Integer> tmp = list;
            int size = tmp.size();
            list = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                Integer cur = tmp.get(i);
                for (Integer next : g[cur]) {
                    if (next == n - 1) {
                        return res;
                    }
                    if (!visited[next]) {
                        visited[next] = true;
                        list.add(next);
                    }
                }
            }
        }
    }

    public int[] shortestDistanceAfterQueries(int n, int[][] queries) {
        List<Integer>[] g = new ArrayList[n];
        for (int i = 0; i < g.length; i++) {
            g[i] = new ArrayList<>();
            g[i].add(i + 1);
        }
        int ql = queries.length;
        int[] res = new int[ql];
        for (int i = 0; i < ql; i++) {
            g[queries[i][0]].add(queries[i][1]);
            res[i] = bfs(g);
        }
        return res;
    }

    public int bfs(List<Integer>[] g) {
        int res = 0, n = g.length;
        Queue<Integer> q = new ArrayDeque<>();
        q.offer(0);
        here:
        while (!q.isEmpty()) {
            int size = q.size();
            Set<Integer> set = new HashSet<>();
            for (int i = 0; i < size; i++) {
                int cur = q.poll();
                if (cur == n - 1) {
                    break here;
                }
                set.addAll(g[cur]);
            }
            q.addAll(set);
            res++;
        }
        return res;
    }

}

性能

1547.切棍子的最小成本

目标

有一根长度为 n 个单位的木棍，棍上从 0 到 n 标记了若干位置。例如，长度为 6 的棍子可以标记如下：

给你一个整数数组 cuts ，其中 cuts[i] 表示你需要将棍子切开的位置。

你可以按顺序完成切割，也可以根据需要更改切割的顺序。

每次切割的成本都是当前要切割的棍子的长度，切棍子的总成本是历次切割成本的总和。对棍子进行切割将会把一根木棍分成两根较小的木棍（这两根木棍的长度和就是切割前木棍的长度）。请参阅第一个示例以获得更直观的解释。

返回切棍子的最小总成本。

示例 1：

输入：n = 7, cuts = [1,3,4,5]
输出：16
解释：按 [1, 3, 4, 5] 的顺序切割的情况如下所示：
第一次切割长度为 7 的棍子，成本为 7 。第二次切割长度为 6 的棍子（即第一次切割得到的第二根棍子），第三次切割为长度 4 的棍子，最后切割长度为 3 的棍子。总成本为 7 + 6 + 4 + 3 = 20 。
而将切割顺序重新排列为 [3, 5, 1, 4] 后，总成本 = 16（如示例图中 7 + 4 + 3 + 2 = 16）。

示例 2：

输入：n = 9, cuts = [5,6,1,4,2]
输出：22
解释：如果按给定的顺序切割，则总成本为 25 。总成本 <= 25 的切割顺序很多，例如，[4, 6, 5, 2, 1] 的总成本 = 22，是所有可能方案中成本最小的。

说明：

2 <= n <= 10^6
1 <= cuts.length <= min(n - 1, 100)
1 <= cuts[i] <= n - 1
cuts 数组中的所有整数都互不相同

提示：

Build a dp array where dp[i][j] is the minimum cost to achieve all the cuts between i and j.
When you try to get the minimum cost between i and j, try all possible cuts k between them, dp[i][j] = min(dp[i][k] + dp[k][j]) + (j - i) for all possible cuts k between them.

思路

有一个长度为 n 的木棍，刻度从 0 ~ n，有一个整数数组 cuts，cuts[i] 表示需要在刻度 i 处进行切割，切割的成本为该刻度所在棍子的长度，求切割棍子的最小成本。

许多算法书上引入动态规划经常举的一个例子是钢条切割问题。已知特定长度钢条的价值，问怎样切可以使价值最大。而本题是给出必须要切的点，问按照什么顺序切成本最小。

定义 dp[i][j] 表示完成 (i, j) 之间所有切割点所需要的最小成本，dp[0][n] 就是答案。状态转移方程为 dp[i][j] = min(dp[i][k] + dp[k][j]) + j - i)。根据定义 dp 数组应该初始化为 0，因为无法切割时成本为 0。

但是由于切割点的范围太大 2 ~ 10^6，如果直接定义的话会超出内存限制。可以先将切割点排序，定义 i，j 为切点的下标，切点个数 m 最大为 100，时间复杂度为 O(m^3)。

考虑到切点本身不包含木棍的两个端点 0 和 n，我们定义端点 endpoint 数组，将这两个端点加进来，dp[0][m - 1] 即为所求。状态转移方程为 dp[i][j] = min(dp[i][k] + dp[k][j]) + endpoint[j] - endpoint[i]。

特别需要注意的是 dp 数组的遍历的顺序。当我们计算 dp[i][j] 时需要已经计算出 dp[k][j]，枚举起点 i 应该倒序，因为 k > i，同理还需要计算出 dp[i][k]，枚举终点 j 应该正序，因为 k > y。枚举 k 正序倒序都可以。

枚举 i，j 的先后顺序也是可以交换的。

代码


/**
 * @date 2024-11-11 10:07
 */
public class MinCost1547 {

    public int minCost(int n, int[] cuts) {
        Arrays.sort(cuts);
        int m = cuts.length;
        int[] endpoint = new int[m + 2];
        System.arraycopy(cuts, 0, endpoint, 1, m);
        endpoint[m + 1] = n;

        m = endpoint.length;
        int[][] dp = new int[m][m];

        for (int i = m - 3; i >= 0; i--) {
            for (int j = i + 2; j < m; j++) {
                int min = Integer.MAX_VALUE;
                for (int k = i + 1; k < j; k++) {
                    min = Math.min(dp[i][k] + dp[k][j], min);
                }
                dp[i][j] = min + endpoint[j] - endpoint[i];
            }
        }
        return dp[0][m - 1];
    }

}

性能

638.大礼包

目标

在 LeetCode 商店中，有 n 件在售的物品。每件物品都有对应的价格。然而，也有一些大礼包，每个大礼包以优惠的价格捆绑销售一组物品。

给你一个整数数组 price 表示物品价格，其中 price[i] 是第 i 件物品的价格。另有一个整数数组 needs 表示购物清单，其中 needs[i] 是需要购买第 i 件物品的数量。

还有一个数组 special 表示大礼包，special[i] 的长度为 n + 1 ，其中 special[i][j] 表示第 i 个大礼包中内含第 j 件物品的数量，且 special[i][n] （也就是数组中的最后一个整数）为第 i 个大礼包的价格。

返回确切满足购物清单所需花费的最低价格，你可以充分利用大礼包的优惠活动。你不能购买超出购物清单指定数量的物品，即使那样会降低整体价格。任意大礼包可无限次购买。

示例 1：

输入：price = [2,5], special = [[3,0,5],[1,2,10]], needs = [3,2]
输出：14
解释：有 A 和 B 两种物品，价格分别为 ¥2 和 ¥5 。 
大礼包 1 ，你可以以 ¥5 的价格购买 3A 和 0B 。 
大礼包 2 ，你可以以 ¥10 的价格购买 1A 和 2B 。 
需要购买 3 个 A 和 2 个 B ， 所以付 ¥10 购买 1A 和 2B（大礼包 2），以及 ¥4 购买 2A 。

示例 2：

输入：price = [2,3,4], special = [[1,1,0,4],[2,2,1,9]], needs = [1,2,1]
输出：11
解释：A ，B ，C 的价格分别为 ¥2 ，¥3 ，¥4 。
可以用 ¥4 购买 1A 和 1B ，也可以用 ¥9 购买 2A ，2B 和 1C 。 
需要买 1A ，2B 和 1C ，所以付 ¥4 买 1A 和 1B（大礼包 1），以及 ¥3 购买 1B ， ¥4 购买 1C 。 
不可以购买超出待购清单的物品，尽管购买大礼包 2 更加便宜。

说明：

n == price.length == needs.length
1 <= n <= 6
0 <= price[i], needs[i] <= 10
1 <= special.length <= 100
special[i].length == n + 1
0 <= special[i][j] <= 50
生成的输入对于 0 <= j <= n - 1 至少有一个 special[i][j] 非零。

思路

有一个购物清单 need，need[i] 表示需要购买商品 i 的数量，price[i] 表示商品 i 的单价，此外还有一组大礼包 special，special[j][i] 表示大礼包 j 中包含的第 i 件商品的数量，并且 specal[j][n] 表示该大礼包的价格。求购买 need 清单中的商品最少花费多少钱，我们可以购买大礼包任意次，但是购买的总数量不能超过需求的数量，尽管可能价格更低。

完全背包问题是物品有无限个，背包容量有限，求能装下的最大价值/最小价值。如果将题目中的清单视为多个背包容量，单买物品 i，以及购买大礼包 j 中的商品 i 视为不同的商品，那么我们求的是装满所有背包的最小价值。问题在于，大礼包不光有商品 i，还有其它商品，如何处理？

网友题解将单买也看成大礼包，只不过其它商品数量为 0，这样可以统一处理大礼包。

// todo

代码

性能

3259.超级饮料的最大强化能量

目标

来自未来的体育科学家给你两个整数数组 energyDrinkA 和 energyDrinkB，数组长度都等于 n。这两个数组分别代表 A、B 两种不同能量饮料每小时所能提供的强化能量。

你需要每小时饮用一种能量饮料来最大化你的总强化能量。然而，如果从一种能量饮料切换到另一种，你需要等待一小时来梳理身体的能量体系（在那个小时里你将不会获得任何强化能量）。

返回在接下来的 n 小时内你能获得的最大总强化能量。

注意你可以选择从饮用任意一种能量饮料开始。

示例 1：

输入：energyDrinkA = [1,3,1], energyDrinkB = [3,1,1]
输出：5
解释：
要想获得 5 点强化能量，需要选择只饮用能量饮料 A（或者只饮用 B）。

示例 2：

输入：energyDrinkA = [4,1,1], energyDrinkB = [1,1,3]
输出：7
解释：
第一个小时饮用能量饮料 A。
切换到能量饮料 B ，在第二个小时无法获得强化能量。
第三个小时饮用能量饮料 B ，并获得强化能量。

说明：

n == energyDrinkA.length == energyDrinkB.length
3 <= n <= 10^5
1 <= energyDrinkA[i], energyDrinkB[i] <= 10^5

思路

有 energyDrinkA 和 energyDrinkB 两个数组，表示饮料 A 和 B 在第 i 小时可以提供的能量，现在需要每一小时饮用饮料 A 或 B 来获取能量，可以暂停一小时来切换饮料，求能够获得的最大能量。

定义 dp[i][j] 表示第 i 小时选择饮料 j 所能获取的最大能量，假设 j = 0 表示饮料 A，j = 1 表示饮料 B，那么状态转移方程为 dp[i][0] = Math.max(dp[i - 1][1], dp[i - 1][0] + energyDrinkA)，dp[i][1] = Math.max(dp[i - 1][0], dp[i - 1][1] + energyDrinkB)，最终返回 Math.max(dp[n - 1][0], dp[n - 1][1])。初始条件 dp[0][0] = energyDrinkA[0] dp[0][1] = energyDrinkA[1]。

由于只与前面的状态有关，因此可以进行存储优化，使用两个变量保存前一个小时饮用 A B 的最大能量即可。

代码


/**
 * @date 2024-11-01 0:37
 */
public class MaxEnergyBoost3259 {

    public long maxEnergyBoost_v1(int[] energyDrinkA, int[] energyDrinkB) {
        int n = energyDrinkA.length;
        long prevA = energyDrinkA[0];
        long prevB = energyDrinkB[0];
        for (int i = 1; i < n; i++) {
            long curA = Math.max(prevB,  prevA + energyDrinkA[i]);
            long curB = Math.max(prevA,  prevB + energyDrinkB[i]);
            prevA = curA;
            prevB = curB;
        }
        return Math.max(prevA, prevB);
    }

}

性能

3181.执行操作可获得的最大总奖励II

目标

给你一个整数数组 rewardValues，长度为 n，代表奖励的值。

最初，你的总奖励 x 为 0，所有下标都是未标记的。你可以执行以下操作任意次：

从区间 [0, n - 1] 中选择一个未标记的下标 i。
如果 rewardValues[i] 大于你当前的总奖励 x，则将 rewardValues[i] 加到 x 上（即 x = x + rewardValues[i]），并标记下标 i。

以整数形式返回执行最优操作能够获得的最大总奖励。

示例 1：

输入：rewardValues = [1,1,3,3]
输出：4
解释：
依次标记下标 0 和 2，总奖励为 4，这是可获得的最大值。

示例 2：

输入：rewardValues = [1,6,4,3,2]
输出：11
解释：
依次标记下标 0、2 和 1。总奖励为 11，这是可获得的最大值。

说明：

1 <= rewardValues.length <= 5 * 10^4
1 <= rewardValues[i] <= 5 * 10^4

思路

与昨天的题相比，数据范围变大了。

// todo

代码

性能

3180.执行操作可获得的最大总奖励I

目标

给你一个整数数组 rewardValues，长度为 n，代表奖励的值。

最初，你的总奖励 x 为 0，所有下标都是未标记的。你可以执行以下操作任意次：

从区间 [0, n - 1] 中选择一个未标记的下标 i。
如果 rewardValues[i] 大于你当前的总奖励 x，则将 rewardValues[i] 加到 x 上（即 x = x + rewardValues[i]），并标记下标 i。

以整数形式返回执行最优操作能够获得的最大总奖励。

示例 1：

输入：rewardValues = [1,1,3,3]
输出：4
解释：
依次标记下标 0 和 2，总奖励为 4，这是可获得的最大值。

示例 2：

输入：rewardValues = [1,6,4,3,2]
输出：11
解释：
依次标记下标 0、2 和 1。总奖励为 11，这是可获得的最大值。

说明：

1 <= rewardValues.length <= 2000
1 <= rewardValues[i] <= 2000

思路

有一个长度为 n 的整数数组 rewardValues 和一个变量 x 初始为 0，可以执行任意次操作，每次操作可以从 [0, n - 1] 中选一个未标记的下标 i，如果 rewardValues[i] > x，x += rewardValues[i]，并标记 i。求 x 的最大值。

// todo

2025 年 8 月
一	二	三	四	五	六	日
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30	31