/*
   As duas funções abaixo fazem o mesmo cálculo. 
   Qual das duas implementações é melhor? Qual consome mais memória? 
   Qual é mais rápida e quão mais rápida uma é que a outra? 
   Teste a velocidade das duas funções usando os programas disponíveis 
   na página (por exemplo, dê 15 e 15 como entrada, ou 18 e 18) e a 
   função time do unix, por exemplo.
*/

int f1 (int x, int y) {
  if (x == 1 || y == 1) 
    return 0;
  else 
    return f1(x-1,y) + f1(x,y-1) + x*y;
}

int f2 (int x, int y) {
  int i, j, t[100][100];

  for (i = 1; i <= x; i++)
    t[i][1] = 0;
  for (j = 2; j <= y; j++)
    t[1][j] = 0;

  for (i = 2; i <= x; i++) 
    for (j = 2; j <= y; j++) 
      t[i][j] = t[i-1][j] + t[i][j-1] + i*j;
  return t[x][y];
}