Calculate an element in a matrix in stages using neighbors

Question

I have this Java problem, which I suspect is related to a higher level algorithm, but my searches could not come up with anything practical.

You create an array as follows:

1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 

Basically, A _{i, j} = A _{i-1, j-1} + A _{i-1, j} . It should return an element at the index (l, c): for (4, 1) it should return 4, (5, 2) it returns 10, etc. My solution is simple, but not enough:

 static long get(int l, int c){ long[][] matrix = new long[l+1][l+1]; matrix[0][0]=1; matrix[1][0]=1; matrix[1][1]=1; for(int i=2;i<=l;i++){ matrix[i][0]=1; for(int j=1;j<=i;j++){ matrix[i][j] = matrix[i-1][j-1]+matrix[i-1][j]; } } return matrix[l][c]; } 

It does not work with large values ​​of l and c. Using BigInteger does not work. My searches led me to warp and scan loops, but I don’t know where to start. Any guidance in the right direction is truly appreciated.

PS: Sorry for the new vibe, this is my first question!

Answer 1

You describe the Pascal Triangle for which there is a closed formula:

 matrix[n][k] = n!/(k! * (nk)!) 

PS If these numbers seem familiar, this is because they are also from the binomial theorem , where there are common examples:

 (x+y)^2 = 1* x^2 + 2xy + 1*y^2 (x+y)^3 = 1*x^3 + 3*xy^2 + 3yx^2 + 1*y^3 

Answer 2

You do not need to use a loop, it is just a pascal triangle , the formula is:

 (n, k) = n! / ( k! * (nk)!) 

Will generate your answer for position (n, k).

Answer 3

Try the following:

 static long get(int l, int c) throws Exception { if (l != c) throw new Exception("l != c"); long[][] matrix = new long[l+1][l+1]; matrix[0][0]=1; for (int i = 1; i <= l; ++i) { for (int j = 0; j <= i; ++j) { if (j - 1 >= 0) { matrix[i][j] = matrix[i - 1][j] + matrix[i - 1][j - 1]; } else { matrix[i][j] = matrix[i - 1][j]; } } } return matrix[l][c]; }