以后争取每天搞一题

[效云 李]

编辑距离问题：下面是我的代码，望大家多多指教，多练以后
// 动态规划-编辑距离问题.cpp : Defines the entry point for the console
application.
//

#include "stdafx.h"
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;

void calculate(vector<vector<int> >& f,vector<char> s1,vector<char>
s2,int s1length,int s2length)
{
int i,j;

for(i=0;i<s1length;i++)
{
f[i][0]=i;
}

for(j=0;j<s2length;j++)
{
f[0][j]=j;
}

for(i=1;i<s1length;i++)
{
for(j=1;j<s2length;j++)
{
int temp=f[i-1][j]+1;
if(temp>(f[i][j-1]+1))
{
temp=f[i][j-1]+1;
}
if(temp>f[i-1][j-1]+(s1[i]==s2[j]?0:1))
{
temp=f[i-1][j-1]+(s1[i]==s2[j]?0:1);
}
f[i][j]=temp;
}
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int s1length,s2length;
ifstream finput;
finput.open("input.txt");
finput>>s1length;
vector<char> s1(s1length);
int i;
char temp;
for(i=0;i<s1length;i++)
{
finput>>temp;
s1[i]=temp;
}

finput>>s2length;
vector<char> s2(s2length);
for(i=0;i<s2length;i++)
{
finput>>temp;
s2[i]=temp;
}
finput.close();

vector<vector<int> > f(s1length,vector<int>(s2length));
calculate(f,s1,s2,s1length,s2length);
cout<<f[s1length-1][s2length-1];
/*for(i=0;i<s2length;i++)
{
cout<<s2[i]<<endl;
}
*/

system("pause");
return 0;
}

[朱涛]

怎么只有答案没有题目呀？

--

朱涛
中科院软件所基础软件国家工程中心
http://twitter.com/towerjoo

2009/4/9 效云 李 <lixiao...@gmail.com>

[higer]

你能不能把你的题贴上来，说清楚你的程序要解决的问题。

[higer]

看了一下你的算法，写的的确比我的精炼，而且里面对“动态规划”的算法理解的比较好。学习......
现在说说我对动态规划算法的一些体会：
1 对于一道题，如何知道这道题是否应该使用“动态规划”的算法，需要考虑该题是否具有两种性质：
1） 最优子结构性质
2） 子问题重叠性质

2 那么知道了要使用动态规划算法，应该如何去应用呢？我觉得，与其性质对应，从两点入手：
1） 寻找它的子结构性质，也就是类似(i,j)、(i-1,j)、(i,j-1)、(i-1,j-1)之间的关系
2） 继续提炼，归纳出子问题的递归结构，也就是一些嵌套的for循环了

[李效云]

对，你说的很有道理，但他妈的，确实，最优子结构那步抽象比较难想啊，日啊。
那步抽象也是关键，现在没什么好办法，只有通过习题，从经典例题里找类似的，看别人怎么解决，然后学习，我想这也是大量练习的必要性所在啊，赶紧把王晓东那书搞完，如果有时间多搞几遍，熟能生巧！赶紧赶紧，以后见算法题目就杀，马上就要找工作了，又是一次高考啊，杀啊！

2009/4/12 higer <higerin...@gmail.com>