本篇小鸡汤：待到苦尽甘来时，我给你讲讲来时路。

 欢迎拜访：羑悻的小杀马特.-CSDN博客

本篇主题：解答洛谷的最优包含问题

制作日期：2024.12.23

隶属专栏：C/C++题海汇总

 ​​

目录

 本篇简介：

一·动态规划简述： 

1.1概念：

1.2基本原理：

 1.3使用步骤：

1.3.1定义状态：

1.3.2确定状态转移方程：

1.3.3确定初始状态：

1.3.4计算最终结果：

1.4应用场景： 

1.4.1资源分配问题：

​编辑​1.4.2最长公共子序列问题：

​编辑​

1.4.3字符串编辑距离问题：

二·题目叙述：

 ​编辑​

三·思路简述： 

四·解答代码：

五·动态规划算法基于本篇的总结：

 本篇简介：

通过对动态规划的理解，来利用状态转移方程，填充好dp二维数组，完成对本题：最优包含的解答，理解为什么这么列方程，以及其他的一些细节处理是怎么做到的。

一·动态规划简述： 

1.1概念：

动态规划（Dynamic Programming）是一种用于解决优化问题的算法策略。

1.2基本原理：

1.2.1分解问题：​ 1.2.2避免了重复计算：

​

 1.3使用步骤：

1.3.1定义状态：

​

1.3.2确定状态转移方程：

​

1.3.3确定初始状态：

​

1.3.4计算最终结果：

 ​

1.4应用场景： 

1.4.1资源分配问题：

​1.4.2最长公共子序列问题：

​

1.4.3字符串编辑距离问题：

​

也许说了这么大堆，大家还是不太了解，那么我们抛开这些概念，跟着博主的思路，去上手搞一下这道题，也许会慢慢理解自己对它的深奥之处了，这里我们就先记住就是假设前面我们已经知道答案了往后面的答案靠拢（当然也可以是知道后面的答案往前推，这里根据题目具体分析）

二·题目叙述：

 ​

测试用例：

输入：

ABCDEABCD
XAABZ

输出：

3

洛谷原题链接： [蓝桥杯 2019 国 B] 最优包含 - 洛谷

三·思路简述： 

 这道题目简单来说是什么？

就是给了我们两个串一个是主串为s；另一个是子串为t；让我们每次都可以对s操作（也就是把一个字符可以改掉，并且记录操作次数）；最后使得它中存在有一个为t的子串（这里有点不同，它可以不相邻如s：abc ;t:ac 这样也可以的）。

那么此刻我们可能是没有思路，或者直接去说暴力去一个个遍历等，然而这里肯是不合理的；

​ 

看到数据后我们便停止了想法；博主是百般苦思，突然看到了：

​ 

凭之前做动态规划题的思路；一般只要出现最小最大等；肯定与它逃不了干系，然后就是它又是字符串，之前也做了很多关于字符串的动态规划；因此可以把这道题往这方面去想。

 这里由于是两个串，我们不妨设置二维dp；

dp数组含义：

dp[i][j]表示让s下标0-i对应的的子串中存在t的0-j这段串的最小操作次数

然后呢我们就是想方设法得出状态转移方程：

首先肯定大家对这一步很难想；但是这一步说白了它又是解答问题的关键；因此下面博主带大家思考如何写出：

首先我们假设已经到了i，j位置但是不一定s t两个子串同对应位置；然后我们根据这道题的题意可以得出应该是向前推，也就是后序的从前往后初始化dp数组。

下面请看图：

​   

通过上面的作图分析我们就得到了相关状态转移方程咯。

状态转移方程：

​

俗话说的好状态转移方程也算是动态规划问题的关键了。

初始化问题和填充二维dp数组： 

 我们要如何初始化dp数组呢？

首先我们要的是最小值，因此我们可以考虑先把它 初始化都为最大值：

这里博主使用的是memset这个库函数，因为它的对整形数组的值一个一个字节初始化的；因此我们使用的是：

 memset(dp, 0x3f, sizeof(dp));

这样每个整型就初始化成0x3f3f3f3f它不是整型最大值INT_MAX，那为什么不初始化后者呢？

①INT_MAX：

一般用于表示整数的上限，例如在一些需要检查整数是否溢出的情况，如计算两个整数相加时：

#include <iostream>
#include <climits>
int main() {
    int a = INT_MAX;
    int b = 1;
    if (a + b < 0) {
        std::cout << "Overflow occurred!" << std::endl;
    }
    return 0;
}

解释：上述代码检查 a + b 是否小于 0，因为如果 a 为 INT_MAX 且 b 为正数，它们相加会导致溢出，结果为负数，利用这个特性可以检测溢出。

②0x3f3f3f3f:

​ 1·在算法和动态规划中经常被用作一个较大的数，但又不是 INT_MAX 那么大。使用 0x3f3f3f3f 作为一个很大的数有一些优点。
 2·它是一个方便的数字，在使用 memset 函数初始化数组时，使用 memset(arr, 0x3f, sizeof(arr)) 可以将数组初始化为一个较大的值，而且两个 0x3f3f3f3f 相加不会溢出。
 

#include <iostream>
#include <cstring>
int main() {
    int arr[5];
    memset(arr, 0x3f, sizeof(arr));
    std::cout << arr[0] << " " << arr[1] << std::endl;
    int sum = 0x3f3f3f3f + 0x3f3f3f3f;
    std::cout << sum << std::endl;
    return 0;
}

解释：这段代码中，memset(arr, 0x3f, sizeof(arr)) 把 arr 数组中的元素初始化为 0x3f3f3f3f，0x3f3f3f3f + 0x3f3f3f3f 相加结果不会溢出，而如果使用 INT_MAX 相加会溢出。

 总结：
 INT_MAX 是 int 类型能表示的最大值，常用于表示整数范围的上限和溢出检查；
 0x3f3f3f3f 是一个很大的数，但比 INT_MAX 小，常用于算法中作为一个较大的初始值，尤其是在使用 memset 等函数初始化数组时，因为其具有方便计算和不易溢出的特点
下面就初始化完了吗，当然不是：

因为我们这样就会产生与定义不符；我们就看状态方程发现可以从1开始双层for循环遍历，当它下标是0难道一定符合题意吗？

 对于dp[0][j]：就是从s中的0个字符去找让它变成t中的前j个字符，然而明显是不可能的；故我们如果把它设置成很大的值这里把它想象成无穷大还是可以的。
但是对于dp[i][0]：这样还可以吗？肯定不行，因为这明显不用操作就好，因此还需要这种情况改成0。 

这样初始化就ok咯。

后面还有个优化处理：

我们为了让s[i],t[j]让它们下标正好对应的是第几个元素，有在前面加了个空字符（相当于虚拟节点）：

 s = " " + s;//这里前面补上“ ”让后面访问s[i]，t[j]直接就是它的第几个
 t = " " + t;

填充dp二维数组： 
此时就用我们的状态转移方程完成就好了。

下面我们就可以手搓出代码了吧；但是当博主根据测试范围给它卡空间开dp会发现有溢出风险：

这里由于我们会返回dp[n1][n2]；最大不就才1000嘛；首先如果我们开1001理论可以的，但是就会 出现：

但尝试把它开大一个1002就可以了，可能有预留空间的意思把。

四·解答代码：

#include <bits/stdc++.h>
using namespace std;
//最值问题且为字符串，不妨动态规划：
//dp[i][j]表示让s下标0-i对应的的子串中存在t的0-j这段串的最小操作次数
int main() {
    string s, t;
    cin >> s >> t;
    s = " " + s;//这里前面补上“ ”让后面访问s[i]，t[j]直接就是它的第几个
    t = " " + t;
    int n1 = s.size();
    int n2 = t.size();
    int dp[1002][1002];//多开一个，这里1001可能越界
    memset(dp, 0x3f, sizeof(dp));//初始化max因为要求min；
    //而且符合了题意比如dp[0][j]：这里表示从s的0-0；让它存在t的0-j；
    //这肯定是不存在的故可以想象成操作+oo才达到
    for (int i = 0; i <= n1; i++) dp[i][0] = 0;//符合一下定义
    //从s的0-i找t的0-0肯定是不用操作故为0
    for (int i = 1; i <= n1; i++) {
        for (int j = 1; j <= n2; j++)
        dp[i][j] = s[i] == t[j]? dp[i - 1][j - 1] : min(dp[i - 1][j - 1] + 1, dp[i - 1][j]);

    }
    cout << dp[n1][n2];
    return 0;
}

最终也是通过了：

 干货来袭：

五·动态规划算法基于本篇的总结：

 根据博主个人做了的动态规划题总结了几点，希望对大家学习这块有帮助：

1·联想到动态规划---->2·确定好状态转移方程(确定的时候根据题意判断是从前往后还是从后往前然后去找i-1或者i+1)---->3·初始化防越界（这里可以是一维dp或者二维dp，有可能原数组和dp数组下标不是一一对应关系，因此要处理好）----> 4·填充dp数组（根据状态转移方程，这里可能是从前往后遍历，也可以是从后往前遍历，根据题目具体分析）---->5·确定返回值---->6·再次检查dp数组是否还会存在越界---->7·可以选择做好滚动数组优化处理。

本篇的要点也就全部结束了，最后再次感谢大家的阅读，希望对大家学习动态规划以及基于这道题解答对大家有所帮助，感谢支持！！！ 

​