LeetCode周记 EP1

字数统计: 4.1k字   |   阅读时长: 17分

前言

新开一个系列，LeetCode刷题周记，每周刷题有感悟可以总结一下。

本周主题：记忆化搜索、动态规划、01背包

题目：

  • 240609每日一题—Burst Balloons
  • 240608双周赛最后两题—Find the Maximum Length of a Good Subsequence
  • 240609周赛最后两题—Maximum Total Reward Using Operations

    记忆化搜索

    Burst Balloons
    You are given n balloons, indexed from 0 to n - 1. Each balloon is painted with a number on it represented by an array nums. You are asked to burst all the balloons.

    If you burst the ith balloon, you will get nums[i - 1] nums[i] nums[i + 1] coins. If i - 1 or i + 1 goes out of bounds of the array, then treat it as if there is a balloon with a 1 painted on it.

    Return the maximum coins you can collect by bursting the balloons wisely.

这道题的第一个关键思路是逆向思维，戳气球的操作会导致两个气球从不相邻变成相邻，使后续操作处理困难，将戳气球的过程反过来看成每次添加一个气球，直到形成原数组。定义方法 $solve$，令 $solve(i,j)$ 表示将开区间 $(i,j)$ 内的位置全部填满气球能够得到的最多硬币数。由于是开区间，因此区间两端的气球的编号就是 $i$ 和 $j$，对应着 $val[i]$ 和 $val[j]$。

第二个思路比较简单，在原数组左右各增加一个$1$，即左右边界时的得分。

下面，对于$solve(i,j)$：

  • 当 $i≥j−1$ 时，开区间中没有气球，$solve(i,j)$ 的值为 0；
  • 当 $i<j−1$ 时，我们枚举开区间内的全部位置 $mid$，令 $mid$ 为当前区间第一个添加的气球，该操作能得到的硬币数为 $val[i]×val[mid]×val[j]$。同时我们递归地计算分割出的两区间对 $solve(i,j)$ 的贡献，这三项之和的最大值，即为 $solve(i,j)$ 的值。这样问题就转化为求 $solve(i,mid)$ 和 $solve(mid,j)$ ，可以写出方程：

由于在枚举mid的过程中，一定会产生相同子区间，即存在重复计算，此时可以采用记忆化的方式存储计算结果，优化时间复杂度。

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
32
33
34
35
36
37
38
class Solution {
    public int[][] rec;
    public int[] val;

    public int maxCoins(int[] nums) {
        int n = nums.length;
        val = new int[n + 2]; // 增加边界
        for (int i = 1; i <= n; i++) {
            val[i] = nums[i - 1];
        }
        val[0] = val[n + 1] = 1;
        rec = new int[n + 2][n + 2]; // 记忆化
        for (int i = 0; i <= n + 1; i++) {
            Arrays.fill(rec[i], -1);
        }
        return solve(0, n + 1);
    }

    public int solve(int left, int right) {
        if (left >= right - 1) {
            return 0;
        }
        if (rec[left][right] != -1) {
            return rec[left][right]; // 已计算
        }
        for (int i = left + 1; i < right; i++) {
            int sum = val[left] * val[i] * val[right];
            sum += solve(left, i) + solve(i, right);
            rec[left][right] = Math.max(rec[left][right], sum);
        }
        return rec[left][right];
    }
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/burst-balloons/solutions/336390/chuo-qi-qiu-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

背包DP

有 $n$ 个物品和一个容量为 $W$ 的背包，每个物品有重量 $w_{i}$ 和价值 $v_{i}$ 两种属性，要求选若干物品放入背包使背包中物品的总价值最大且背包中物品的总重量不超过背包的容量。

0-1背包

在上述例题中，若每个物体只有两种可能的状态（取与不取），对应二进制中的 0 和 1，这类问题便被称为「0-1 背包问题」。

例题中已知条件有第 $i$ 个物品的重量 $w_{i}$，价值 $v_{i}$，以及背包的总容量 $W$。

设 DP 状态 $f_{i,j}$ 为在只能放前 $i$ 个物品的情况下，容量为 $j$ 的背包所能达到的最大总价值。

考虑转移。假设当前已经处理好了前 $i-1$ 个物品的所有状态，那么对于第 $i$ 个物品，当其不放入背包时，背包的容量不变，背包中物品的总价值也不变，故这种情况的最大价值为 $f_{i-1,j}$；当其放入背包时，背包的容量会增大 $w_{i}$，即前一个状态的背包容量必须是 $j-w_{i}$，通过本轮加上 $w_{i}$ 达到 $j$，同时背包中物品的总价值会增大 $v_{i}$，故这种情况下的最大价值为 $f_{i-1,j-w_{i}}+v_{i}$。

由此可以得出状态转移方程：

依据该状态转移方程可以写出解法1:

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
int n = w.length;
// 容量维度多开辟一个位置，因为要用索引表示容量，需要匹配到 W
int[][] dp = new int[n][W+1];
// 初始化
// 对于dp[0][j]，所有j<w[0]的位置初始化为0，其余位置初始化为 v[0]
for(int j=0;j<=W;j++){
    if(j<w[0]){
        dp[0][j] = 0;
    }else{
        dp[0][j] = v[0];
    }
}
// 对于dp[i][0]，背包容量为0时无法装物，价值为0，对于其余位置，是由其上层的状态计算出的，也一并初始化为0
for(int i=1;i<n;i++){
    Arrays.fills(dp[i], 0);
}
// 计算
for(int i=1;i<n;i++)
{
    for(int j=1;j<=W;j++)
    {
        if(j>=w[i]) dp[i][j]=Math.max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);
        else dp[i][j]=dp[i-1][j];
    }
}
// dp[n-1][W]即为结果

如果直接采用二维数组对状态进行记录，可能会出现 MLE（Memory Limit Exceeded）。可以考虑改用滚动数组的形式来优化。

滚动数组

在动态规划问题中，通常需要存储一系列状态值，每个状态值可能依赖于前几个状态。随着计算的进行，较早的状态值可能不再需要。例如，在求解斐波那契数列时，只需要保留最近两个值即可计算下一个值，之前的值则可以被覆盖重用。

思想：通过观察dp方程来判断需要使用哪些数据，可以抛弃哪些数据，一旦找到关系，就可以用新的数据不断覆盖旧的数据量来减少空间的使用。

由于在二维解法中，对于当前层（当前物品）状态有影响的只有上一层（前一物品），即对 $f_i$ 有影响的只有 $f_{i-1}$，则可以去掉第一维，用一个重复更新的一维数组记录状态，直接用 $f_{j}$ 来表示处理到当前物品时背包容量为 $j$ 的最大价值，得出以下方程：

这里，$f_{j-w_i} + v_i$代表如果选择放入第$i$个物品，则在背包容量为$j-w_i$时的价值加上这个物品的价值。而$max$操作保证了在是否选择放入第$i$个物品之间取最优解。

大部分背包问题的转移方程都是在此基础上推导出来的。

对于代码实现方面，滚动数组的实现要注意内层循环应从后向前逆序遍历，这可以避免在 $j\geqslant w_{i}$ 时，$f_{i,j}$ 被 $f_{i,j-w_{i}}$ 所影响，即避免小背包容量下取物对后续大背包容量下状态计算的影响。

举例来说，假设物品4的重量为$1$，在二维解法中dp[4][5]应该由dp[3][5]和dp[3][4]得出，dp[4][6]应该由dp[3][6]和dp[3][5]得出，而在正序遍历的一维解法中，f[5]会先被计算，可能存在f[5]存储dp[3][4]状态的情况，此时f[6]的计算就无法获取dp[3][5]，造成计算错误。这个计算错误事实上是对同一物品的多次装包，因为dp[3][4]表示取物品4(下标为3)，若下一步f[6]再选择f[5]+v[3]则表示又取了一次物品4，这在01背包中是不允许的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
using namespace std;
const int maxn = 13010;
int n, W, w[maxn], v[maxn], f[maxn];

int main() {
  cin >> n >> W;
  for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];  // 读入数据
  for (int i = 1; i <= n; i++)
    for (int l = W; l >= w[i]; l--) // l >= w[i]保证背包能装下，防止越界
      if (f[l - w[i]] + v[i] > f[l]) f[l] = f[l - w[i]] + v[i];  // 状态方程
  cout << f[W];
  return 0;
}

// 错误的：
// for (int i = 1; i <= n; i++)
//   for (int l = 0; l <= W - w[i]; l++)
//     f[l + w[i]] = max(f[l] + v[i], f[l + w[i]]);

完全背包

完全背包模型与 0-1 背包类似，与 0-1 背包的区别仅在于一个物品可以选取无限次，而非仅能选取一次。

可以借鉴 0-1 背包的思路，进行状态定义：设 $f_{i,j}$ 为只能选前 $i$ 个物品时，容量为 $j$ 的背包可以达到的最大价值。需要注意的是，虽然定义与 0-1 背包类似，但是其状态转移方程与 0-1 背包并不相同。

可以考虑一个朴素的做法：对于第 $i$ 件物品，枚举其选了多少个来转移。这样做的时间复杂度是 $O(n^3)$ 的。

状态转移方程如下：

考虑进行优化。可以发现，对于 $f_{i,j}$，只要通过 $f_{i,j-w_i}$ 转移就可以了。因此状态转移方程为：

理由是当我们这样转移时，$f_{i,j-w_i}$ 已经由 $f_{i,j-2\times w_i}$ 更新过，那么 $f_{i,j-w_i}$ 就是充分考虑了第 $i$ 件物品所选次数后得到的最优结果。换言之，我们通过局部最优子结构的性质重复使用了之前的枚举过程，优化了枚举的复杂度。与 0-1 背包相同，我们可以将第一维去掉来优化空间复杂度。

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
using namespace std;
const int maxn = 1e4 + 5;
const int maxW = 1e7 + 5;
int n, W, w[maxn], v[maxn];
long long f[maxW];

int main() {
  cin >> W >> n;
  for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];
  for (int i = 1; i <= n; i++)
    for (int l = w[i]; l <= W; l++)
      if (f[l - w[i]] + v[i] > f[l]) f[l] = f[l - w[i]] + v[i];  // 核心状态方程
  cout << f[W];
  return 0;
}

例题1: Maximum Total Reward Using Operations

Maximum Total Reward Using Operations I & II

You are given an integer array rewardValues of length n, representing the values of rewards.

Initially, your total reward x is 0, and all indices are unmarked. You are allowed to perform the following operation any number of times:

  • Choose an unmarked index i from the range [0, n - 1].
  • If rewardValues[i] is greater than your current total reward x, then add rewardValues[i] to x (i.e., x = x + rewardValues[i]), and mark the index i.

Return an integer denoting the maximum total reward you can collect by performing the operations optimally.

首先，rewardValues中的数应该从小到大选，于是可以对其进行排序。排序后，可以看作01背包问题处理，背包的重量限制转化成了rewardValues[i]与rewardx的制约关系。因此定义 f[i][j] 表示选取前i个rewardValues下x能达到的最大值j。由于x所能达到的最大值不确定，在实现中应选取一个尽可能大的值。

考虑转移，对于f[i][j]，是否选择rewardValues[i]：

  • 不选，f[i][j] = f[i-1][j]，即分数与上轮相同。
  • 选择，f[i][j] = f[i-1][j-rewardValues[i]]，即上一轮的分数 j-rewardValues[i] 必须满足 j-rewardValues[i]<rewardValues[i], 同时为防止越界，j-rewardValues[i]需要大于等于0。综上，需满足 rewardValues[i] <= j < 2*rewardValues[i]。

这里由于f[i][j]不需要存储“价值”，j自然表示了可以达到的最大值，因此f[i][j]通过布尔值表示是否可达即可，则有f[i][j] = f[i-1][j] || f[i-1][j-rewardValues[i]]。

写出二维解法如下：

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
32
33
34
35
36
37
// author: SilenceZheng66
class Solution {
    public int maxTotalReward(int[] rewardValues) {
        int n = rewardValues.length;
        int m = 10000;
        // int m = Integer.MAX_VALUE;

        // 对物品从小到大排序
        Arrays.sort(rewardValues);
        
        // 全部初始化为false
        boolean[][] dp = new boolean[n][m];
        // 初始化第一行
        dp[0][0] = true; // 不选
        dp[0][rewardValues[0]] = true; // 选

        // 开始计算dp数组
        for(int i=1;i<n;i++){
            // 初始化第一列，即一直不选。
            dp[i][0] = true;
            // 对于[1, rewardValues[i]]区间，复制上一层表示可以不选。
            for(int j=1;j<rewardValues[i];j++){
                dp[i][j] = dp[i-1][j];
            }
            // 对于可选取区间，计算新得分。
            for(int j=rewardValues[i];j<2*rewardValues[i];j++){
                dp[i][j] = (dp[i-1][j] || dp[i-1][j-rewardValues[i]]);
                // if(dp[i][j]) System.out.println(i+", "+j);
            }
        }
        // 返回最后一行的最大真值
        for(int i=m-1;i>=0;i--){
            if(dp[n-1][i]) return i;
        }
        return 0;
    }
}

二维解法对于数据范围大的情况会存在MLE，因此参照01背包问题，考虑使用滚动数组进行优化。原计算可以简化为：f[j] = f[j] || f[j-rewardValues[i]]，同时注意逆序遍历。另外，由于最终结果可以由j的值表示，故可以进一步优化数组为位运算，采用一个BigInteger表示布尔数组。

下面考虑如何用位运算表示布尔运算，假设之前已经遍历过的元素为1, 2, 3，则此时状态应为：0000 0011 1111，即可达分数区间为[0, 5]，此时假设下一个元素为5，则需要对区间[5, 10)进行布尔计算，计算的本质是将当前状态的区间[0, 5)与区间[5, 10)进行or运算。因此可以通过构造一个“把区间[0, 5)移动到区间[5, 10)位置上且其余部分为0”的mask来与原状态进行or运算，既计算了目标区间，又不影响其他状态。构造的方法是先构造区间[0, 5)上全为1的mask，而后与原状态进行and操作提取目标区间，再将目标区间左移到[5, 10)的位置上得到最终的mask。

对于上面的例子来说，我们首先构造一个初始mask0000 0000 0001，而后对其左移rewardValues[i]位，这里即$5$位，得到0000 0001 0000，减$1$得到目标区间全真值mask0000 0000 1111，再左移rewardValues[i]位到目标区间，得到0001 1110 0000，与原状态进行or运算，得到：0001 1111 1111，即可取的分数范围为[0, 8]，符合题意。参考代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
import java.math.BigInteger;

class Solution {
    public int maxTotalReward(int[] rewardValues) {
        BigInteger f = BigInteger.ONE;
        for (int v : Arrays.stream(rewardValues).distinct().sorted().toArray()) {
            BigInteger mask = BigInteger.ONE.shiftLeft(v).subtract(BigInteger.ONE);
            f = f.or(f.and(mask).shiftLeft(v));
        }
        return f.bitLength() - 1;
    }
}

例题2: Find the Maximum Length of a Good Subsequence

Find the Maximum Length of a Good Subsequence I & II

You are given an integer array nums and a non-negative integer k. A sequence of integers seq is called good if there are at most k indices i in the range [0, seq.length - 2] such that seq[i] != seq[i + 1].

Return the maximum possible length of a good subsequence of nums.

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

Good Subsequence通俗理解一下就是一个有不超过k个前后不相同元素对的子序列，即题目需要在元素尽可能少不同的情况下使子序列尽可能的长。

这道01背包没想清楚，先来特殊思路：处理相邻元素不同的DP问题

把有$k$个相邻下标元素不同的子序列称为k序列。用 $c n t[k]$ 记录以 $x$ 结尾的 $k$ 序列的最大长度。考虑以 $nums[i]$ 结尾的 $k$ 序列, $nums [i]$ 要么接在以 $nums[i]$ 结尾的 $k$ 序列后，要么接在某个以 $n u m sj$ 结尾的 $k-1$ 序列后。所以状态转移方程即为

这里我们不需要关心是否 $n u m s[j] \neq n u m s[i]$ ，即 $k-1$ 序列是否已经以 $nums[i]$ 结尾，因为在同样以 $nums[i]$ 结尾的情况下， $k-1$ 序列的长度一定小于 $k$ 序列的长度。

$c n t[k-1]$ 的最大值可以在哈希表基础上维护值有序来实现。但实际上，我们不需要维护 $c n t[k-1]$ 的所有值, 由于 $k-1$ 序列的最大长度单调不减, 所以只需要维护 $c n t[k-1]$ 的最大值就可以了。

在一些要求相邻状态不同的DP问题中，在处理当前状态时，不一定非要与所有前置状态比较, 只需要记录 $d p$ 最大和次大值对应的前置状态即可。这样的思路同样适用于本题。

注意由于$nums[i]$的范围比较大，Java实现的时候要用Map来存防止OOM。

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
// author: SilenceZheng66
class Solution {
    public int maximumLength(int[] nums, int k) {
        Map<Integer, Map<Integer, Integer>> cnt = new HashMap<>();
        int[] mx = new int[k + 1];

        for (int i = 0; i <= k; i++) {
            cnt.put(i, new HashMap<>());
        }

        for (int x : nums) {
            for (int kk = k; kk >= 0; kk--) {
                // 考虑到更新顺序，需要倒序枚举
                int currentValue = kk>0?mx[kk - 1]:0;
                currentValue = Math.max(currentValue, cnt.get(kk).getOrDefault(x, 0))+1;
                cnt.get(kk).put(x, currentValue);
                mx[kk] = Math.max(mx[kk], cnt.get(kk).getOrDefault(x, 0));
            }
        }
        return getMax(mx);
    }

    private int getMax(int[] mx) {
        int max = 0;
        for (int value : mx) {
            max = Math.max(max, value);
        }
        return max;
    }
}

参考文献

[1] https://oi-wiki.org/dp
[2] https://leetcode.cn/problems/maximum-total-reward-using-operations-ii/solutions/2805413/bitset-you-hua-0-1-bei-bao-by-endlessche-m1xn/
[3] https://blog.csdn.net/txyyt_wst/article/details/130206572
[4] https://blog.csdn.net/m0_46427179/article/details/107419492
[5] https://leetcode.cn/problems/find-the-maximum-length-of-a-good-subsequence-ii/solutions/2805181/chu-li-xiang-lin-yuan-su-bu-tong-de-dpwe-gobq/

后记

首发于 silencezheng.top，转载请注明出处。

关于最后一个例题我自己的思考如下（不知道为什么是错的），没时间浪费了先存档以后再思考，先理解正确解法：

Good Subsequence通俗理解一下就是一个有不超过k个前后不相同元素对的子序列，即题目需要在元素尽可能少不同的情况下使子序列尽可能的长。

由于 k 是非负整数，因此长度等于 1 的子序列一定是好子序列。对于任意一个子序列，在后面添加一个元素之后，子序列的长度增加 1，相邻不同元素对的数量不变或增加 1，因此可以使用动态规划计算最长好子序列的长度。

由于是”子序列“问题，其实也还是从全集中选择若干元素的问题，由于元素不能重复选，则还是0-1背包问题。这里背包的重量限制转化为前后不相同元素对数量的限制，对于元素x = nums[i]，定义dp[i][j]为遍历前i个元素时前后不相同元素对数量不超过j时的子序列最大长度。

TODO:如果定义为前i个元素，则实现时遇到相等长度情况应该如何处理？即dp[a][j]==dp[b][j]，如果只取最后一个，那么后面和dp[?][j-1]比的时候也是相同亦可？

这里需要注意一下如何定义，参考01背包问题，“前i个元素”一致，“背包容量”与“前后不相同元素对数量”一致，且此约束条件应转换为不超过j而不是等于j。

则对于x的选取分为三种情况：

  1. 不选，dp[i][j] = dp[i-1][j]；
  2. 选择，且x与子序列的前一个数相同，则dp[i][j] = dp[?][j]+1；
  3. 选择，且x与子序列的前一个数不同，则dp[i][j] = dp[?][j-1]+1。

这里使用了?来表示前一个数y的下标，y需要通过遍历得到。

由此可以得到状态转移方程为：

  • 情况A（不选）：dp[i][j] = dp[i-1][j]+1
  • 情况B（选）：dp[i][j] = max(dp[?][j], dp[?][j-1])+1
赏

谢谢打赏哟！

支付宝
微信

扫一扫，分享到微信

微信分享二维码
本站总访问量次 |

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

SilenceZheng66<br><br>记录所学技术<br>谢谢浏览