DP中明明只需要最终结果的啊。。。为啥要浪费个数组空间记住方案选择。。。


拿两个题目分析好了。

1.最大k乘积问题

问题描述：

设I是一个n(n≤10)位的十进制整数。如果将I划分成k段，则可得到k个整数。这k个整数的乘积称为I的一个k乘积。设计一个算法，对于给定的I和k，求出I的最大k乘积及相应的划分方法。

提示：

称整数I的最高位到最低位（个位）依次为第0位至第n-1位， 设I(s,t)表示整数I的从s位开始的t位数字组成的整数，f(i,j)表示I(0,i)的最大j乘积（即整数I最左侧i位的最大j乘积），则f(i,j)可按下式递归计算。

可按上式依次计算：

f(2,2),f(3,2),…,f(n,2)

f(3,3),f(4,3),…,f(n,3)

…

f(k,k),f(k+1,k),…,f(n,k)

f(n,k)即为整数I的最大k乘积。

用a(i,j)记录使f(i,j)取得最大值的m, 从a(n,k)开始可反推得到I的划分方法。设i为整数当前剩余的位数（初始时i=n）, j为剩余整数要划分的段数（初始时 j=k）,于是可确定一个划分段为I(a(i,j), i- a(i,j))，划分完后整数剩余i= a(i,j)位, 剩余的划分段数j=j-1, 重复上述过程，直到i>0, j=1为止。

 

输入数据：

文件名：input.txt

第一行2个数，分别是整数I的位数n和划分段数k，用空格分隔；

第二行为整数I。

输出数据

文件名：output.txt

第一行，整数I的最大k乘积；

第二行，整数I的划分情况，共k段，段间用空格分隔。

输入输出样例：

输入：input.txt

6 4

253187

输出：output.txt

59472

2 531 8 7

方法都告诉你了哈~下面先贴代码再解释： 


/*

	变量定义说明：
	
	a[i]表示该数的第i位是多少
	digit[i][j]表示该数的第i位到第j位的数是多少，
		如样例中digit[2][4]为531
	dp[i][j]为前i位中，添加了j-1个乘积可以取到的最大值，
		当然，dp[i][1]为前i位中添加0个括号（也就是不添加括号，也就是分成一段）。那么就是digit[1][i]。这就是初始化
	mp[i][j]为前i位中，添加了j-1个乘号的第j-1个乘号放在了哪儿（待会输出方案的时候要用）
*/ 

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int maxn=10; 
char s[maxn+10];
int a[maxn+10];
int dp[maxn+10][maxn+10];
int digit[maxn+10][maxn+10];
int mp[maxn+10][maxn+10];

int GetDigit(int i,int j){
	int num=0;
	for(int k=i;k<=j;k++) num=num*10+a[k];
	return num;
}

void PrintAns(int i,int j){
	if (j==1){
		printf("%d",digit[1][i]);
		return;
	}
	int k=mp[i][j];
	PrintAns(k,j-1);
	printf(" %d",digit[k+1][i]);
}

int main(){
	freopen("input.txt","r",stdin);
	int n,m;
	int i,j,k,len;
	while(scanf("%d%d",&n,&m)!=EOF){
		scanf("%s",s);
		for(i=1;i<=n;i++) a[i]=s[i-1]-'0';
		//for(i=1;i<=n;i++) printf("%d\n",a[i]);
		memset(dp,0,sizeof(dp));
		memset(mp,0,sizeof(mp));
		//初始化: 
		for(i=1;i<=n;i++) dp[i][1]=dp[i-1][1]*10+a[i];
		//for(i=1;i<=n;i++) printf("%d\n",dp[i][1]);
		
		//计算digit值：
		for(i=1;i<=n;i++)
			for(j=i;j<=n;j++)
				digit[i][j]=GetDigit(i,j);
		
		//计算dp值：				
		for(len=2;len<=m;len++)
			for(j=len;j<=n;j++)
				for(k=1;k<j;k++)
					if (dp[k][len-1]*digit[k+1][j]>dp[j][len]){
						//如果更大，那么记录值和插入乘号的位置
						dp[j][len]=max(dp[j][len],dp[k][len-1]*digit[k+1][j]);
						mp[j][len]=k;
					}
					
		printf("%d\n",dp[n][m]);
		
		//for(i=1;i<=n;i++)
		//	for(j=1;j<=m;j++)
		//		printf("%d%c",mp[i][j],j==m?'\n':' ');
		
		//for(i=1;i<=n;i++)
		//	for(j=1;j<=m;j++)
		//		printf("%d%c",dp[i][j],j==m?'\n':' ');
		PrintAns(n,m);
		printf("\n");
	}
	return 0;
}

/*
	第一重循环控制的是插入的乘号的个数，从0个乘号到m-1个乘号
	第二重控制的是终点的位置
	第三重控制的是乘号可以插入的地方
	（如果想不懂想想dp[3][2]怎么算：dp[3][2]=max{dp[1][1]*digit[2][3],dp[2][1]*dp[3][3]},再不懂再算几个）

	接下来是输出方案：递归m次即可，每次找到当前步骤的乘号插入的地方递归进入，回溯时候输出该数
	递归语句为查找下一个乘号在哪，该数为digit[当前的乘号插入值][当前的末尾值]
*/



2.编辑距离问题。

问题描述：

设A和B是2个字符串（长度不超过255字符），我们要用最少的字符操作将字符串A转换为字符串B。这里所说的字符操作是指：（1）删除一个字符，（2）插入一个字符，（3）将一个字符改为另一个字符。将字符串A转换为字符串B所用的最少字符操作数称为字符串A到B的编辑距离，记为δ(A, B)，试设计一个动态规划算法，对任给的2个字符串A和B，计算出它们的编辑距离δ(A, B)。

提示：

设所给的两个字符串为A[1..m]和B[1..n]，定义D[i,j]= δ(A[1..i], B[1..j])。单个字符a，b间的距离定义为：

考察从字符串A[1..i]到B[1..j]的变换，有以下几种情况：

（1）将字符A[i]改为字符B[j]；需δ(A[i], B[j])次操作；

（2）删除字符A[i]；需1次操作；

（3）插入字符B[j]；需1次操作；

因此，D[i,j]可递归地定义为：

D[i,j]=min{D[i-1,j-1]+ δ(A[i], B[j]), D[i-1,j]+1, D[i,j-1]+1}，c[i,j]= δ(A[i], B[j])

D[i,0]=i，c[i,j]=2，i=0~m;

D[0,j]=j，c[i,j]=3，j=0~n；

其中c[i,j]记录了D[i,j]取最小值的三种情况之一。

最优值δ(A, B)=D[m,n]。从c[m,n]开始可反推出A到B的转换方案。

 

输入数据：

文件名：input.txt

第一行，字符串A；

第二行字符串B；

输出数据

文件名：output.txt

第一行，字符串A与B的编辑距离；

第二行，说明，固定为“[x1y]--将x改为y，[2x]--删除x，[3x]--插入x”

第三行，从字符串A向B的转换过程。

输入输出样例：

输入：input.txt

The book ishere.

Here is thebook.

输出：output.txt

13

[x1y]--将x改为y，[2x]--删除x，[3x]--插入x

[2T][h1H]e[2 ][2b][2o][o1r][k1e] is [3t]he[3 ][3b][3o][r1o][e1k].

 

这题简单在方法都告诉你了，难在过程怎么输出的。方法跟题1一样，认真分析题1解法就自然懂了~下面贴代码： 


#include<map>
#include<set>
#include<math.h>
#include<time.h>
#include<queue>
#include<stack>
#include<cstdio>
#include<string>
#include<cstdlib>
#include<cstring>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;

const int maxn=505;
const int maxm=505;
const int INF=99999999;
#define eps 1e-6
#define input freopen("input.txt","r",stdin)
#define output freopen("output.txt","w",stdout)

char a[maxn],b[maxn];
int dp[maxn][maxn];
int mp[maxn][maxn];
/*mp[i][j]:
	0.说明a[i]与b[j]已经匹配 
	1.字母a[i]改为b[j]
	2.插入b[j]
	3.删除a[i]
*/ 

void GetAns(int x,int y){
	if (x<1&&y<1) return;
	if (mp[x][y]==0) GetAns(x-1,y-1);
	else if (mp[x][y]==1){
		GetAns(x-1,y-1);
		printf("[%c1%c]",a[x],b[y]);
	}
	else if (mp[x][y]==2){
		GetAns(x,y-1);
		printf("[3%c]",b[y]);
	}
	else{
		GetAns(x-1,y);
		printf("[2%c]",a[x]);
	}
	return;
}

int main(){
	//input; 
	int n,m,i,j;
	gets(a+1);
	gets(b+1);
	memset(dp,0,sizeof(dp));
	n=strlen(a+1);
	m=strlen(b+1);
	
	if (a[1]==b[1]) dp[1][1]=0;
	else{
		dp[1][1]=1;
		mp[1][1]=1;
	}
	
	for(i=2;i<=n;i++){
		dp[i][1]=dp[i-1][1]+1;
		mp[i][1]=3;
	}
	for(j=2;j<=m;j++){
		dp[1][j]=dp[1][j-1]+1;
		mp[1][j]=2;
	}
	
	for(i=2;i<=n;i++)
	for(j=2;j<=m;j++)
		if (a[i]==b[j]){
			dp[i][j]=dp[i-1][j-1];
			mp[i][j]=0;
		}
		else{
			//dp[i][j]=min(dp[i-1][j-1],min(dp[i][j-1],dp[i-1][j]))+1;
			if (dp[i-1][j-1]<=dp[i][j-1]&&dp[i-1][j-1]<=dp[i-1][j]){
				dp[i][j]=dp[i-1][j-1]+1;
				mp[i][j]=1;
			}
			else if (dp[i][j-1]<=dp[i-1][j-1]&&dp[i][j-1]<=dp[i-1][j]){
				dp[i][j]=dp[i][j-1]+1;
				mp[i][j]=2;
			}
			else{
				dp[i][j]=dp[i-1][j]+1;
				mp[i][j]=3;
			}
		}
	
	/*for(i=1;i<=n;i++)
	for(j=1;j<=m;j++)
		printf("%d%c",dp[i][j],j==m?'\n':' ');*/
	printf("%d\n",dp[n][m]);
	GetAns(n,m);
	return 0;
}