public class EX32011 {
    static int max(int a,int b) {
	return a>b?a:b;
    }
    static public int gainMax(int [][]grille,int i,int j,int [][]gain,boolean [][]gainDisponible) {
	System.out.println("gainMax("+i+","+j+")");
	// Si on est en première ligne alors on connait le gain...
	if (i==0) return grille[i][j];
	// Si c'est déjà connu pourquoi se fatiguer ?
	if (gainDisponible[i][j]) return gain[i][j];
	// Sinon, cherchons le gain à partir de la case juste au-dessus
	int v = gainMax(grille,i-1,j,gain,gainDisponible);
	// Comparons avec le gain de la case au-dessus à gauche (si elle existe)
	if (j>0) v = max(v,gainMax(grille,i-1,j-1,gain,gainDisponible));
	// Comparons avec le gain de la case au-dessus à droite (si elle existe)
	if (j<grille[i].length-1) v = max(v,gainMax(grille,i-1,j+1,gain,gainDisponible));
	// Le gain total est le coût de la case courante additionné du
	// meilleur des gains au-dessus et en plus maintenant c'est connu
	gainDisponible[i][j] = true;
	gain[i][j] = grille[i][j]+v;
	return gain[i][j];
    }
    static public int gainMax(int [][]grille) {
	// Structures pour la programmation dynamique
	int [][]gain = new int[grille.length][grille.length];
	boolean [][]gainDisponible = new boolean[grille.length][grille.length];

	// Calculons le gain de la première case de la dernière ligne
	int v = gainMax(grille,grille.length-1,0,gain,gainDisponible);
	    System.out.println();
	// Comparons avec les gains des autres cases de la dernière ligne
	for (int j=1; j<grille[0].length; j++) {
	    v = max(v,gainMax(grille,grille.length-1,j,gain,gainDisponible));
	    System.out.println();
	}
	return v;
    }
    static public void main(String []a) {
	int [][]grille = { { 1,2,3}, {6,5,4}, {7,8,9} };
	int v = gainMax(grille);
	System.out.println("Résultat = "+v);
    }
}