動的計画法 練習 - プログラム倉庫

class dp{

String str;
String ph;
int strlong,nlong;
int sx,nx,nxs;
int dicnumber;
String[] dic=new String[100];
double[] p=new double[100];
double[][] v=new double[500][5];
int[] op=new int[500];
int[][] nextgo=new int[500][5];


double v1,maxv,supv;

double p1;
int t;

void makedata(String str){

strlong=str.length();

ph=str.substring(0,1);


p1=p[0];
for(sx=1;sx<dicnumber+1;sx++){
if(ph.equals(dic[sx]))p1=p[sx];
}

v[0][0]=p1;
v[0][1]=1;

for(t=1;t<strlong-1;t++){
nlong=t;
if(nlong>4)nlong=4;
maxv=-999;
nxs=0;
for(nx=0;nx<nlong+1;nx++){
ph=str.substring(t-nx,t+1);
p1=p[0];
for(sx=1;sx<dicnumber+1;sx++){
if(ph.equals(dic[sx]))p1=p[sx];
}
v1=p1*v[t-1][nx];
if(v1>maxv)nxs=nx;
if(v1>maxv)maxv=v1;
}
v[t][0]=maxv;
nextgo[t][0]=nxs;
for(nx=1;nx<nlong+1;nx++){
v[t][nx]=v[t-1][nx-1];
nextgo[t][nx]=nx-1;
}
}

t=strlong-1;
nlong=strlong-1;
if(nlong>4)nlong=4;
supv=-999;
nxs=0;
for(nx=0;nx<nlong+1;nx++){
ph=str.substring(t-nx,t+1);
p1=p[0];
for(sx=1;sx<dicnumber+1;sx++){
if(ph.equals(dic[sx]))p1=p[sx];
}
v1=p1*v[t-1][nx];
if(v1>supv)nxs=nx;
if(v1>supv)supv=v1;
}

op[t-1]=nxs;
System.out.println(op[t-1]);
t=strlong-2;
while(t<1){
t=t-1;
nx=op[t];
op[t-1]=nextgo[t][nx];
System.out.println(t);
System.out.println(op[t-1]);
}


}




}