Dynamic Programming Problem Notes
2024-03-21 23:24:45 # Algorithm #DP

动态规划问题

判断是否能使用dp：

  • 一个状态是由前面的某个状态或某些状态得到的，且不用关心前面的这些状态是如何得来的。
  • 确定dp[i][j][k]..[l]，就是确定i,j,k,l这些状态是否能通过前面的i,j,k,l的来得到。因此可以定义出dp函数的定义、应该是几纬和动态转移方程。
  • 另一种定义状态的方式是看你要当前的答案需要关注哪些状态，哪些状态会影响到当前的答案（如股票问题的dp状态方程定义）
  • 通常是求最值、方法数

记忆化搜索

模版

1
2
3
4
5
6
7
8
9
10
11
12
int[][] memo = new int[n];
public int dfs(int[] nums1, int i){
  if(i<0){
    //此处代表整个数组已经处理完毕
    return 1;
  }
  if(memo[i]!=-1){
    return memo[i];
  }
  //......
  return memo[i];
}

转移为递推须知

  • 快速边界修改：
    • 转换递推后如果出现memo[i][j-1]的情况，可以把整个第二维度(j)+1，注意第一维度(i)不用变化。相当于是把整个数组往后挪了一位。
    • 出现memo[m-1][n-1] 我们都统一+1，变成memo[i][j], memo[i][j-1], memo[m-1][n]
    • 这种方法不需要修改for loop的index，也不需要做特殊判断
    • 如果是数字的，也要修改！！比如在递归里面我们是判断if(i<0){return 0},正常会写成memo[-1]，但因为我们将数组扩了1位，因此这个地方需要变成memo[0]
    • 一些特殊情况： 在初始化的时候，我们要注意看for loop里的值是从哪里开始循环的，如果本来就是i=0开始的，其实就不需要写成i+1了
    • 简单来说就是把数组退后了一位，其他所有地方都要看情况修改。还有一种情况就是memo[i+1][j+1]的话，可以把数组扩大1位，但是不用修改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
/** 记忆化例子 **/
public int dfs(int[] nums1, int[] nums2, int i, int j){
  if(i<0){
    //这里的i<0在转化成递推且+1后，就变成了index = 0
    return j+1;
  }
  if(j<0){
    //这里的j<0在转化成递推且+1后，就变成了index = 0
    return i+1;
  }
  memo[i][j] = dfs(i-1,j) + dfs(i,j-1);
}

/** 转移成递推二维后的初始化：**/
int[] memo = new int[nums1.length+1][nums2.length+1];
for(int j = 0;j<nums2.length;j++){
  //i为0而不是-1，因为数组往后移动了1位
  memo[0][j+1] = j+1;
}
for(int i = 0; i<nums1.length;i++){
  //j为0而不是-1，因为数组往后移动了1位
  memo[i+1][0] = i+1;
}
// 这里为了防止边界问题两个维度都加了1
for(int i = 0;i<nums1.length;i++){
  for(int j = 0;j<nums2.length;j++){
    memo[i+1][j+1] = memo[i][j+1] + memo[i+1][j];
  }
}
  • 转换成一维也有需要注意的地方
    • 当memo[i][0]变成了memo[0]时，我们需要在下面dp的i的for循环下进行更新，因为这样才能保证每一步都有正确的值（否则会被上一次的更新覆盖掉）

一维例子：

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
/** 原来的二维 **/
int[] memo = new int[nums1.length+1][nums2.length+1];
for(int j = 0;j<nums2.length;j++){
  memo[0][j+1] = j+1;
}
for(int i = 0; i<nums1.length;i++){
  memo[i+1][0] = i+1;
}
// 这里为了防止边界问题两个维度都加了1
for(int i = 0;i<nums1.length;i++){
  for(int j = 0;j<nums2.length;j++){
    memo[i+1][j+1] = memo[i][j+1] + memo[i+1][j];
  }
}

/** 转化成一维 **/
int[] memo = new int[nums1.length+1][nums2.length+1];
for(int j = 0;j<nums2.length;j++){
  memo[j+1] = j+1;
}
// 这里为了防止边界问题两个维度都加了1
for(int i = 0;i<nums1.length;i++){
  //此处更新
  memo[0] = i+1;
  for(int j = 0;j<nums2.length;j++){
    memo[j+1] = memo[j+1] + memo[j];
  }
}

背包问题

从一个数组中，或者从一个固定范围的元素中，取出一些没有必要连续的元素，让他们的和【恰好】【至多】【至少】为k

0/1背包

背包容量为capacity，给一堆物品，每个物品的重量为w[i]，问你恰好装满整个背包的话能有多少【方案数】

1
2
3
# 本质上是选/不选的问题，且每个物品只能被选一次
# 不选当前物品i / 选当前物品i
dfs(i-1,c) + dfs(i-1,c-w[i])

注意【恰好】可以改成至多、至少，这些直接在递归入口进行逻辑判断

完全背包

背包容量为capacity，给一堆物品，每个物品的重量为w[i]，问你恰好装满整个背包的话能有多少【方案数】（每种物品可以选无数次）

1
2
3
# 本质上是选/不选的问题，且每个物品每一轮都可以被选
# 不选当前物品i / 选当前物品i=》上一轮物品i还是可以作为candidate
dfs(i-1,c) + dfs(i,c-w[i])

最长公共子序列(LCS)

简称LCS

1
2
3
4
5
6
7
8
9
10
# 本质上是选/不选的问题
if s[i]==s[t]:
  # i和t都选，所以+1
  # 不用判断dfs(i,j-1)和dfs(i-1,j),即不需要考虑只选一个的情况
	res = dfs(i-1,j-1)+1
else:
  # 不用判断dfs(i-1,j-1),即不需要考虑两个都不选的情况，因为已经被包含
  # dfs(i-1,j)，丢掉i，i不包含在lcs里面
  # dfs(i,j-1)，丢掉j，j不包含在lcs里面
  res = max(dfs(i-1,j),dfs(i,j-1))

类似习题

  • 1458. Max Dot Product of Two Subsequences
    • LCS问题中，我们寻找的是长度，每个匹配项贡献的是固定值（即+1），因此不需要考虑“只选择当前i和j”的情况，因为长度的增加总是基于两个序列中相对应位置的元素匹配。
    • 最大点积子序列问题中，我们寻找的是最大化数值（点积），这个值是变化的，取决于具体的元素值。因此，考虑“只选当前的i和j”是有意义的，因为它们单独的点积可能就是最大的，不需要依赖于它们之前的元素。

编辑距离

1
2
3
4
5
6
7
8
9
10
11
12
# 删除、插入、替换的操作次数
# 本质上也是选/不选的问题
# 删除和插入实际上是一样的
if s[i]==s[t]:
  # i和j都不需要额外操作（无需+1），那么答案依赖于子问题dfs(i-1,j-1)
  res = dfs(i-1,j-1)
else:
  # dfs(i-1,j): 对i进行操作，比如删除和插入,那么答案依赖于子问题dfs(i-1,j)
  # dfs(i,j-1): 对j进行操作, 比如删除和插入，那么答案依赖于子问题dfs(i,j-1)
  # dfs(i-1,j-1): i和j都选，实际上就是替换操作，将i替换成j，或将j替换成i
  # 以上的操作都会+1
  res = max(dfs(i-1,j),dfs(i,j-1),dfs(i-1,j-1))+1

最长递增子序列(LIS)

选出来的递增子序列必须是严格递增的，通常有两种方法

  • dp
1
2
3
4
5
6
7
8
9
10
11
int[] dp = new int[n];
for(int i = 0;i<n;i++){
  int res = 0;
  //去遍历之前的数，找到能够满足条件的元素，然后构成子序列
  for(int j = 0;j<i;j++){
    if(nums[j]<nums[i]){
      res = Math.max(dp[j],res);
    }
  }
  dp[i] = res + 1;
}
  • 贪心+二分
    • 在java中我们维护一个数组arr，数组需要保证严格递增，假设j为数组arr目前的最后一个元素，如果nums[i]>arr[j]，则直接加入数组中，相反使用二分法找到第一个大于nums[i]的数，并将其替换。
    • 这个方法依赖于贪心策略：使得长度为i+1的数组中的最后一个元素最小，这样才有可能构造更长的子序列
    • 最后答案为j+1 =>这个j+1是代表整个数组中的最长递增子序列，不代表是nums[i]为最后一个元素的最长递增子序列！
    • 如果要更新i结尾元素的最长递增子序列，要根据nums[i]所被替换或插入的index来

这类题型可以有很多变形，最常见的就是值递增，或通过排序后满足某种特定的“有一致性、传递性的条件”来求最大长度等等

俄罗斯套娃问题

  • 假设m为宽度，n为高度，按宽度排序，宽度相同时按高度下降排序，这样做的好处是我们只比较高度n时，能够避免将相同宽度的信封算进去。
  • 相似问题
    • 1626. Best Team With No Conflicts
      • 虽然这道题没有很明显的递增，但是我们也是有条件可以看出来递增的：当一名年龄较小球员的分数严格大于一名年龄较大的球员，则存在矛盾。 所以，在按年龄排序的情况下，score要递增；在按score排序的情况下，年龄要递增。这就是我们判断他是否“递增”的条件。

股票系列问题

简单来说就是状态机DP

  • 持有/未持有
  • 第i天
  • 第k次交易
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
39
40
41
42
43
44
45
46
47
/** 这是没有冷冻期的情况 **/
int[][] memo = new int[n][2];
public int dfs(int[] prices, int i, boolean hold){
  if(i<0){
    //第-1天不可能开始买股票，持有股票的这种情况是不存在的
    return hold==true?Integer.MIN_VALUE:0;
  }
  if(memo[i][hold]!=-1) return memo[i][hold];
  if(hold){
    return memo[i][hold] = Math.max(dfs(prices,i-1,true), dfs(prices,i-1,false) - prices[i]);
  }
  return memo[i][hold] = Math.max(dfs(prices,i-1,false), dfs(prices,i-1,true) + prices[i]);
}

/** 有冷冻期的情况 **/
public int dfs(int[] prices, int i, boolean hold){
  //......
  if(hold){
    //这里的i-2代表前天卖掉了，所以要个冷冻期
    return memo[i][hold] = Math.max(dfs(prices,i-1,true), dfs(prices,i-2,false) - prices[i]);
  }
  //因为买入是不算冷冻期的，所以不需要i-2
  return memo[i][hold] = Math.max(dfs(prices,i-1,false), dfs(prices,i-1,true) + prices[i]);
  
/** 有K次交易限制的情况 **/

public int dfs(int[] prices, int i, int hold, int k){
  //表示在第0天以前，还没开始的时候
  //因此不可能有hold的情况
  if(k<0){
      return Integer.MIN_VALUE;
  }
  if(i<0){
      return hold==1? Integer.MIN_VALUE : 0;
  }
  if(memo[i][k][hold]!=-1){
      return memo[i][k][hold];
  }
  if(hold==1){
      //卖一次算k
      memo[i][k][hold] = Math.max(dfs(prices,i-1,1,k),dfs(prices, i-1, 0,k)-prices[i]);
  }else{
      //k-1表示已经用掉了一次
      memo[i][k][hold] = Math.max(dfs(prices,i-1,0,k),dfs(prices,i-1,1,k-1)+prices[i]);
  }
  return memo[i][k][hold];
}
  • 在Leetcode 121中，我们被要求最多只能交易一次，这实际上是和最多交易k次的模版一样的

区间DP

本质上也是选与不选的问题，通常与palindrome、分割区间有关

分割区间的小tip

Prev
2024-03-21 23:24:45 # Algorithm #DP
Next