s and t are two strings.
Change string s into string t in the least steps.
In each step you can insert or delete a char of the string.
INPUT n1 s
n2 t
n1 is the length of string s
n2 is the length of string t
OUT the least steps
exp:
INPUT 4 abcd
6 aefbhd
OUT 4
#include<iostream>
#include<string>
using namespace std;
string s1,s2;
int map[100];
int i,j,result[100];
int n1,n2,nc;
int main(){
cin>>n1>>s1>>n2>>s2;
nc=0;
for (i=0;i<n1;i++){
if ((j=s2.find(s1[i]))>=0){
map[nc]=j;
s2.replace(j,1," ");
nc++;
}
}
result[nc-1]=1;
for (i=nc-2;i>=0;i--){
for (j=i+1;j<nc;j++) if ((map[i]<map[j])&&(result[i]<result[j])) result[i]=result[j];
result[i]++;
}
j=0;
for (i=0;i<nc;i++) if(result[i]>j) j=result[i];
cout<<n1+n2-j-j;
system("pause");
return 0;
}
題記：
Python是荷蘭人寫的，Ruby是日本人寫的，Lua是巴西人寫的，我這個中國人只能在這里臉紅。
——CSDN主編 孟巖
不打算自討沒趣地寫個要超過Python,Ruby,Lua的腳本引擎，以鍛煉能力為主。
估計完成以后和Lua有點像，宗旨是：以比Lua更短為榮，以比Python更長為恥 :-)
┏━┓ ┏━━┓ ┏┓
┃┃┣━┳━┫━━╋━┳┳╋╋━┳━━┓
┃ ┫━┃┃┣━━┃┣┫┏┫┃┃┣┓┏┛
┗┻┻┻┫┏┻━━┻━┻┛┗┫┏┛┗┛
┗┛ ┗┛
引擎就叫RapScript好了(Ruby,Lua,Python 加一起)
附上題目：
在一個圓形操場的四周擺放著n堆石子。現要將石子有次序地合并成一堆。規定每次只能選相鄰的2堆石子合并成新的一堆，并將新的一堆石子數記為該次合并的得分。試設計一個算法，計算出將n堆石子合并成一堆的最小得分和最大得分。
/*
Name: Stone Problem
Copyleft: www.graptor.com
Author: Bill Hsu
Date: 27-04-08 15:15
*/
#include <iostream>
#include <string>
#include <fstream>
#define MAX 100
#define MAXint 1000
using namespace std;
int i,j;//循環用的
ifstream in("in.txt");
ofstream out ("out.txt");
int f[MAX][MAX];//f[i][j]表示從i起取j堆的最大值
int sum[MAX][MAX];//sum[i][j]表示從i起取j堆的和
int num[MAX];
int main()
{
int n;
in >>n;
for(i=1;i<=n;i++)
{
in >>num[i];
sum[i][1]=num[i];
f[i][1]=0;
}//end for
for (j=2;j<=n;++j)
{
cout <<endl<<j<<endl<<endl;
for(i=1;i<=n;++i)
{
cout <<(sum[i][j]=num[i]+sum[i%n+1][j-1])<<endl;
}//end for i
}//end for j
int k,x,t;
for (j=2;j<=n;j++)
{
for(i=1;i<=n;i++)
{
f[i][j]=MAXint;
t=sum[i][j];
for(k=1;k<=j-1;k++)
{
x=(i+k-1)%n+1;
if(f[i][k]+f[x][j-k]+t<f[i][j])
f[i][j]=f[i][k]+f[x][j-k]+t;
}//end for k
cout <<f[i][j]<<endl;
}//end for i
}//end for j
int tmp=f[1][n];
for(j=1;j<=n;++j)
{
if (f[j][n]<tmp)
tmp=f[j][n];
}//end for
cout <<tmp<<endl;
system("pause");
return 0;
}//end main
這是Matrix67.com的遞推專項訓練的題目，感覺很好。
*題一：用1 x 1和2 x 2的磁磚不重疊地鋪滿N x 3的地板，共有多少種方案？
樣例輸入：2
樣例輸出：3
先設一個f[i]表示i*3的地板鋪的方法,f[1]=1;f[2]=3;
i*3的地板數是這樣得到的：(i-1)*3的地板比i*3的地板少的地方全鋪上1*1的瓷磚，這有一種鋪法；
或者在(i-2)*3的地板比i*3的地板少的地方鋪上2*2的瓷磚和2個1*1的瓷磚，這有兩種鋪法；
所以得到遞推式：f[i]=f[i-1]+2*f[i-2];
*題二：從原點出發，一步只能向右走、向上走或向左走。恰好走N步且不經過已走的點共有多少種走法？
樣例輸入：2
樣例輸出：7
這個我沒想出來，看題解才弄明白。。
先設一個f[i]表示恰好走i步且不經過已走的點 共有的走法。
如果向上走，不會出現經過已走的點；如果向左或右，上一步不能是向右或左。
引用題解上的一句話：/*
這一步的選擇數= (3*上一步的所有選擇中向上走的選擇數) + (2*上一步的所有選擇中向左、右走的選擇數)。上一步的所有選擇中向上走的選擇數”實際上就是“上上步的所有選擇數”即d[i-2]
*/引用結束
還有一點，就是“上一步的所有選擇中向左、右走的選擇數” 等于 “上步所有的選擇數(即f[i-1])-上步向上的選擇數”
也就等于 “上步所有的選擇數(即f[i-1])-上上步所有的選擇數(即f[i-2])”
所以得到遞推式：f[i] = (3*f[i-2]) + 2*(f[i-1]-f[i-2]);
題解上共有五題，都很好，大家可以去這里看看：
http://www.fengzee.com/blog/article.asp?id=60