动态规划

背包问题

image-20240805162519768

这道题是一个典型的01背包问题，只是在处理的时候遇到了递增和递减的问题，最开始很不理解的原因是我对dp的二维数组填充过程以及依赖关系没有明确清晰的认知，再加上在对找零钱这道题目中有递增操作的影响下，一直没能顺利写出正确的过程来。长话短说，这里主要涉及到一个本回合要选择的价值内容对上一轮次的占用问题。

请看如下期望的递增模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int> f(target + 1, INT_MIN);
f[0] = 0;
int s = 0;
for (int x : nums) {
	for (int j = 1; j <= target; j++) {
		if (j >= x)
		{
			if (f[j - x] != INT_MIN)
			{
				f[j] = max(f[j], f[j - x] + 1); //
			}
		}
		cout << f[j]<<" , ";
	}
	cout << endl;
}
return f[target] > 0 ? f[target] : -1;

image-20240805162926074

在需求的第二行中就出现了 嵌套循环第二层中引用了被之前修改的数据，主要出现在 动态规划朝着 一维滚动数据的优化 的过程中出现的，

再来看所谓的零钱兑换，它并不在乎在本次引用了本次修改的数据，因为一个位置可以重复使用这个特性的存在，使得重复引用变得是重复使用这个索引上的零钱数量。

image-20240805163455560

具体细则

空间优化中的注意事项

image-20240805195501745

递推中的注意事项

image-20240805195825737

同时注意在memo容器中对于初始化值的设定，建议在设定为0

在lamba中与遇见超过 int 与long long 这种涉及越界的问题，建议对加减后变成负数这种情况做出以下限定

image-20240806152854844

同时lamba表达式变量名的申请并不是注明了返回值，需要在实际使用中 -> bool 来进行类型指定，如此，就可以使用 int 中的 0 和 1来代表 bool 中发 false 和 true

经典线性DP

例题

最长公共子序列

思考过程

image-20240806155658543

image-20240806155751436

问题1：公式给定的是x+1个结构必定要比x的结果要大，从给定例子中来看，无论是选或者不选，都会造成结果变小，矛盾。

问题2：靠近下边的菱形结构是在表示如果不相同，则下一轮就会考虑到后面的都不选这种情况，所以不要在不相同的时候考虑问题给定情况

最终公式

image-20240806160646766

一维数组代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int m = text1.length(), n = text2.length();

vector<int> dp(n + 1);
 
	for (char c : text1)
	{
		// int index = c - 'a';
		for (int i = 1, pre = 0; i <= n; ++i)
		{
			int temp = dp[i];
			dp[i] = c == text2[i - 1] ? pre + 1 : max(dp[i], dp[i - 1]);
			pre = temp;
		}
	}
 
	return dp[n];

一维数组优化思考

image-20240806164629202

所以这点跟之前的普通的01背包问题还是存在区别的，这道题目本身对于左边的数据本身就要求是同行的，所以计算后的覆盖才是有效的。

提醒

记忆这种套路的重要目标是 核心公式 的选择思想，不要一上来就尝试套公式，从一开始的分析问题，判断条件是充分且必要的。

例题

712. 两个字符串的最小ASCII删除和

这道题目的核心公式没有太大的改变，依旧是一致就都选上，不一样就分情况迭代。重要的是前置条件的准备，因为最后要求的结果在删除掉的字符的ASCII和的最小值，从这里开始需要有一个条件需要注意一下，有两个字符串，s1 ，s2

s1，s2为空的情况：这种情况对于计算最长相等子串没有影响，最后返回 0 即可，但是本题的需求在一方为空情况下，需要记录的ASCII也会发生改变。

对于s1，s2不同的为空情况，代码实现中都有对应的注释

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//dp 空间优化，还是再强调一次，开始之前要思考
 
		int m = s1.length();
		int n = s2.length();
		vector<int> dp(n + 1);
 
		for (int i = 0; i < n; i++) //在s1为空的情况下，需要将s2逐索引删除的ASCII和递增
		{
			dp[i + 1] = dp[i] + s2[i];
		}
 
		for (char x : s1)
		{
			int pre = dp[0]; //在s2为空的前提下，记录下本次s1逐索引删除到空的ASCII和，但是在这之前要保存对应的左上角
			dp[0] = dp[0] + x;
			for (int i = 1; i <= n; i++)
			{
				int temp = dp[i];
				dp[i] = x == s2[i - 1] ? pre : min(dp[i] + x, dp[i - 1] + s2[i - 1]);
				pre = temp;
			}
		}
 
		return dp[n];

最长递增子序列

300. 最长递增子序列

思考过程

子序列属于子集型问题，解决问题的方式采用子集型回溯，尝试的方式有两种，选择，枚举，这里采用的方式是枚举。

image-20240807153343916

代码

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
	//递归加上记忆化搜索
		vector<int> memo(nums.size());

		function<int(int)> dfs = [&](int i) {
			int& res = memo[i];
			if (res > 0) return res;

			for (int j = 0; j < i; j++)
			{
				if (nums[j] < nums[i])
				{
					res = max(res, dfs(j));
				}
			}
			return ++res;

			};

		int res = 0;
		for (int i = 0; i < nums.size(); i++)
		{
			res = max(res, dfs(i));
		}

		return res;        

//递推
     int n = nums.size();
		
		vector<int> memo(n);
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < i; j++)
			{
				if(nums[j]<nums[i]) 
                {
                    memo[i] = max(memo[i],memo[j]);
                }
			}
			memo[i]++;
		}
		return ranges::max(memo);

这道例题和之前讲过的最长子序列是关联的，将数组排序后再去求得LCS就是LIS。（LCS是最长子序列，LIS是最长递增子序列）。

image-20240807153135739

时间复杂度优化

image-20240807155226654

image-20240807155345407

因为最后重复的子问题，所以最终的解决方法是贪心算法加上二分查找

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
  //额外空间
  vector<int> g;
  for (int x : nums) {
      auto it = ranges::lower_bound(g, x); //在指定的排序完成的容器找找到第一个比x大的数并返回迭代器
      if (it == g.end()) {
          g.push_back(x); // >=x 的 g[j] 不存在
      } else {
          *it = x;
      }
  }
  return g.size();

//原地算法
 auto end = nums.begin();
  for (int x : nums) {
      auto it = lower_bound(nums.begin(), end, x);
      *it = x;
      if (it == end) { // >=x 的 g[j] 不存在
          ++end;
      }
  }
  return end - nums.begin();

状态机

该问题模型可以处理的问题总结

image-20240912154149712