59 lines
1.6 KiB
Java
59 lines
1.6 KiB
Java
import java.util.ArrayList;
|
|
public class MiniMax_versionMemoisation{
|
|
|
|
private static ArrayList<Integer> max = new ArrayList<Integer>();
|
|
private static ArrayList<Integer> min = new ArrayList<Integer>();
|
|
private static int Allumete;
|
|
|
|
public MiniMax_versionMemoisation(int n){
|
|
Allumete = n;
|
|
for(int i=0;i<n;i++){
|
|
max.add(-2);
|
|
min.add(-2);
|
|
}
|
|
}
|
|
|
|
|
|
public static int explorMax(int nbAllumete){
|
|
if (nbAllumete <=0){
|
|
return +1;
|
|
}
|
|
if (max.get(nbAllumete)!=-2){
|
|
return max.get(nbAllumete);
|
|
}
|
|
int meilleurRes = -2;
|
|
for (int coup =1;coup <=3;coup ++){
|
|
int res = explorMin(nbAllumete-coup);
|
|
if (meilleurRes < res){
|
|
meilleurRes =res;
|
|
}
|
|
}
|
|
max.set(nbAllumete,meilleurRes);
|
|
return meilleurRes;
|
|
}
|
|
|
|
|
|
public static int explorMin(int nbAllumete){
|
|
if (nbAllumete <=0){
|
|
return -1;
|
|
}
|
|
if (min.get(nbAllumete)!=-2){
|
|
return min.get(nbAllumete);
|
|
}
|
|
|
|
int mepireRes = 2;
|
|
for (int coup =1;coup <=3;coup ++){
|
|
int res = explorMax(nbAllumete-coup);
|
|
if ( res < mepireRes){
|
|
mepireRes = res;
|
|
}
|
|
}
|
|
min.set(nbAllumete,mepireRes);
|
|
return mepireRes;
|
|
}
|
|
|
|
public static void main(String[]arg){
|
|
MiniMax_versionMemoisation newCLass = new MiniMax_versionMemoisation(1904);
|
|
System.out.println(explorMax(1903));
|
|
}
|
|
} |