最优包含--字符串dp

1.边界--dp【i】【0】=0，空字符串不需要修改

2.状态---修 or 不修

dp[i][j]：s前i个，t前j个

3.转移--  不需要修改，直接取dp[i - 1][j - 1]的值--if（==）

 需要修改，有两种选择：
                // 1. 删除S的第i个字符，对应dp[i - 1][j]
                // 2. 将S的第i个字符修改为T的第j个字符，对应dp[i - 1][j - 1] + 1
                // 取两者中的较小值

P8703 [蓝桥杯 2019 国 B] 最优包含 - 洛谷

#include<bits/stdc++.h>
using namespace std;
#define N 100011
typedef  long long ll;
typedef pair<int,int> pii;
ll dp[1015][1015];
string s,t;
ll mi=0x3f3f3f3f3f3f3f3f;
int main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>s>>t;memset(dp,0x3f,sizeof(dp));// 初始化dp[i][0]为0，表示将S的前i个字符修改为空字符串不需要任何修改for (int i = 0; i <= s.size(); i++) dp[i][0] = 0;// 动态规划计算dp数组的值for (int i = 1; i <= s.size(); i++) {for (int j = 1; j <= t.size(); j++){// 如果S的第i个字符和T的第j个字符相等if (s[i - 1] == t[j - 1]){// 不需要修改，直接取dp[i - 1][j - 1]的值dp[i][j] = min(dp[i][j], dp[i - 1][j - 1]);} else {// 需要修改，有两种选择：// 1. 删除S的第i个字符，对应dp[i - 1][j]// 2. 将S的第i个字符修改为T的第j个字符，对应dp[i - 1][j - 1] + 1// 取两者中的较小值dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1] + 1);}}}for(int i=1;i<=s.size();i++) mi=min(dp[i][t.size()],mi);cout<<mi;return 0;
}