簡單的DP題！不過做得時(shí)候要小心！不然很容易出錯(cuò).
狀態(tài)轉(zhuǎn)移方程為f[i]=max{f[k]+1};{k>=1&&k<=i-1 && f[k]>=0 }
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
char num[101],dict[50001][51],len[50001],map[256];
int f[101],c[101][2],minlen,i,j,k,n;
void init(){
map['i']=map['j']='1';
map['a']=map['b']=map['c']='2';
map['d']=map['e']=map['f']='3';
map['g']=map['h']='4';
map['k']=map['l']='5';
map['m']=map['n']='6';
map['p']=map['r']=map['s']='7';
map['t']=map['u']=map['v']='8';
map['w']=map['x']=map['y']='9';
map['o']=map['q']=map['z']='0';
}
void output(int t){
if(t<1) return ;
output(c[t][0]);
printf("%s ",dict[c[t][1]]);
}
int main(){
init();
while(1){
num[0]='0';// 賦初值，否則strlen(num)返回值一直為1
scanf("%s",num+1);
if(strcmp(num+1,"-1")==0) break;//結(jié)束條件
scanf("%d",&n);
minlen=101;
for(i=1;i<=n;i++) {
scanf("%s",dict[i]);
len[i]=strlen(dict[i]);
if(len[i]<minlen) minlen=len[i];
}
int tmp=strlen(num)-1;
if(minlen>tmp){printf("No solution.\n");continue;}//剪枝
memset(f,-1,sizeof(f));//負(fù)值代表不能由單詞串成
f[0]=0;
int ind;
for(i=minlen;i<=strlen(num)-1;i++){//DP
int min=1000;
for(j=1;j<=n;j++){//枚舉所有的單詞
if(len[j]<=i && map[dict[j][len[j]-1]]==num[i] && f[i-len[j]]>=0){//檢查是否匹配,且只有當(dāng)f[i-len[j]]>=0
int flag=0; //f[i]才可能>=0,否則，f[i]無法由單詞串成
for(k=i;k>=i-len[j]+1;k--){
if(num[k]!=map[dict[j][len[j]-i+k-1]]) {flag=1;break;}
}
if(flag==0 && f[i-len[j]]+1<min) {min=f[i-len[j]]+1;ind=j;}//
}
}
f[i]=min;
if(f[i]==1000) f[i]=-1;
else {c[i][0]=i-len[ind];c[i][1]=ind;}
}
if(f[strlen(num)-1]==-1) printf("No solution.\n");
else {
output(strlen(num)-1);
printf("\n");
}
}
}