Asta e cea mai eficienta metoda la care am ajuns:

int f_mat[0xFFF][0xFFF];/* matricea f */

int f(int i, int j){

return f_mat[i][j];

}

int cost_min[0xFFF]; /* Reprezinta costul minim de la i la n*/

int mincost(int i){

return cost_min[i];

}

int n;

int min(int a, int b) {return a < b ? a : b;}

void gencost(){

/* initializarea cu matricea f */

for(int i = 1; i < n; i++)

 cost_min[i] = f(i,n);

for(int i = n-2; i >= 1; i--){

 /* vedem care e cel mai ieftin mod de a inchiria canoele de la i la n, stiind care sunt cele mai ieftine metode de a le inchiria de la j la n, oricare ar fi j din (i, n) */

 for(int j = n-1; j > i; j--){

  /* incercam sa impartim drumul de la i la n in doua parti: de la i la j si de la j la n, si vedem daca costul se micsoreaza daca este impartit */

  cost_min[i] = min(f(i,j) + mincost(j), mincost(i));

 }

}

/* complexitatea este O( n-1 + (n-2)*(n-1)/2 ) = O( (n-1)*((n-2)/2 + 1) ) = O( (n-1)*(n/2) ) = O( n(n-1)/2 ) = O( n^2 ) */

}