Tính toán phần tử theo ma trận gia tăng, sử dụng hàng xóm

Question

Tôi có vấn đề Java này, mà tôi nghi ngờ nó liên quan đến thuật toán cấp cao hơn, nhưng tìm kiếm của tôi không thể tìm ra bất kỳ thứ gì thực tế.

Bạn xây dựng một mảng như sau:

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

Về cơ bản, A _{i, j} = A _{i-1, j-1} + A _{i-1, j}. Nó phải trả về phần tử tại chỉ mục (l, c): cho (4, 1) nó sẽ trả về 4, (5, 2) trả về 10, vv. Giải pháp của tôi rất đơn giản, nhưng không đủ:

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]; 
} 

Nó không hoạt động với các giá trị lớn của l và c. Sử dụng BigInteger không hoạt động. Tìm kiếm của tôi đã dẫn tôi đến vòng lặp và thu nhỏ, nhưng tôi không biết bắt đầu từ đâu. Bất kỳ chỉ đạo nào đúng hướng đều thực sự được đánh giá cao.

PS: Xin lỗi vì người mới, đây là câu hỏi đầu tiên của tôi!

Answer 1

Bạn đang mô tả Pascal's triangle, mà một công thức khép kín tồn tại:

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

T.B. Nếu những con số này có vẻ quen thuộc, đó là vì họ cũng là từ binomial theorem, nơi mà các ví dụ phổ biến là:

(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

Bạn không cần phải sử dụng một vòng lặp, điều này chỉ đơn giản là pascal's triangle, công thức:

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

Sẽ tạo câu trả lời cho vị trí (n, k).

Answer 3

Hãy thử cách này:

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]; 
}