Peter算法小课堂—动态规划

Peter推荐算法书：《算法导论》

图示：

目录

钢条切割

打字怪人

---

钢条切割

算法导论（第四版）第十四章第一节：钢条切割

题目描述：

给定一根长度为 n?英寸的钢条和一个价格表??，其中 i=1,2,…,n?，求切割方案，使得总销售价格?最大。如果??足够大，最优解可能不需要切割钢条。

这道题可以拆分成两个部分：①总价格最大是多少 ②切割方案

先解决①吧。那么，我们定义一下：f[i]表示长度i的钢条最多能买多少钱。j为切割点。状态转移方程怎么写呢？大家先画一张表格，理解一下含义。

样例：

8

1 5 8 9 10 17 17 20

思考过后，是不是特别有灵感？所以说状态转移方程如下图所示

?

原因：枚举i,j。当分割点在j时，卖的价钱就等于p[j]加上后面的部分的最优值，最后再取个最大值即可。

?所以，①正式解决。②呢？我们再定义一个数组fd[i]，表示计算f[i]的决策时选择切割多少，然后两重循环，循环内判断最大，fd[i]取值即可，代码不告诉了啊，应该大家都会写。

打字怪人

题目描述：你的儿子小明打字水平有限，当他希望打出某个单词如 smart 时，他会错误地按到键盘上其他字母，例如形成 asnmaaaert 这样的尴尬情况。更加令人崩溃的是，小明还不会用"退回"键或者删除功能来清理错误字母。现在小明从一个词汇表里挑了若干个单词进行打字，词汇表里的所有n个单词都已知。请你识别出小明至少打错了几个字符？换句话说，也就是去掉至少几个字符，可以使剩下的内容由词汇表里的真单词拼写出来？

做这道题之前先看看另外一道简单题吧。如下

你的儿子小明打字水平有限，当他希望打出某个单词如 smart 时，他会错误地按到键盘上其他字母键盘，例如形成 asnmaaaert 这样的尴尬情况。更加令人崩溃的是，小明还不会用"退回"键或者删除功能来清理错误字母，现在请你识别出真正单词每个字母在错误单词中的位置。先输入一行字符串，代表小明的打字内容。第二行字符串代表小明真实希望打的单词。小明会确保正确单词所有字母都会依次出现在他打的内容里。

很好，大家已经学会了套娃式建模了，真不戳。这道题使用双游标会更加游刃有余，下面分析控制元素。游标1：指向正确单词中的目标字母等待匹配；游标2：指向打字内容中的字母。那么，请大家思考一下哪个游标是主要游标，哪个是辅助游标呢？当然，游标1每次移动一格时，游标2可能移动若干格。好了，现在代码应该会写了吧。

string a,b;
cin>>a>>b;
int i=0;
for(int j=0;j<b.size();j++){
	while(i<a.size()&&a[i]!=b[j])
		i++;
	cout<<++i<<" ";
}

回到原题。这一题可能需要dp的知识。首先，大家思考一下状态怎么定义？给出两种选择：①f[i]表示前i个字符最少删除几个才能用真实单词拼接②?f[i]表示前i个字符最少删除几个才能用真实单词拼接并确保第i个字母必须保留。思考片刻后，大家不出意外的话应该都会选①。那么，大家真的能快速写出转移方程吗？看来我们要找找规律，那请大家根据1038题的样例输入填写f[i]。

cin>>n>>ls;
cin>>s;
for(int i=1;i<=n;i++) cin>>w[i];
for(int i=1;i<=ls;i++){
	f[i]=f[i-1]+1;
	for(int k=1;k<=n;k++){
		lw=w[k].size();
		int p=search(i,k);
		if(p<0) continue;
		f[i]=min(f[i],f[p]+i-p-lw);
	}
}
cout<<f[ls]<<endl;

请大家思考一下代码的意思。首先，第5行是一个提前处理。然后第6行实际上就是在第一层枚举的字符串后再挨个添加真实单词，search()是从第i个字母往前查找，遇到w[k]起始点时返回（相当于前铺）

int search(int i,int k){
	if(i<lw) return -1;
	if(s[i-1]!=w[k][lw-1]) return -1;
	int pa=i-1;
	for(int pb=lw-1;pb>=0;pb--,pa--){
		while(pa>=0&&s[pa]!=w[k][pb]) pa--;
		if(pa<0) return -1;
	}
	return pa+1;
}

双游标不做解释。

希望这些对大家有用，三连必回