使用鄰居遞增計算矩陣中的元素

Question

我有這個Java問題，我懷疑它涉及到更高級別的算法，但我的搜索沒有能夠提出任何實際的東西。

您構造的陣列如下：

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

基本上，A _I，J = A _I-1，J-1 + A _I-1，J。它應該返回index（l，c）處的元素：for（4,1）它應該返回4，（5,2）返回10等。我的解決方案很簡單，但它不夠：

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

它不適用於較大的l和c值。使用BigInteger不起作用。我的搜索引起了循環偏移和標量化，但我不知道從哪裏開始。任何轉向正確的方向真的很感激。

PS：對於新手感覺不好，這是我的第一個問題！

Answer 1

你所描述Pascal's triangle，爲此閉合式存在：

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

P.S.如果這些數字似乎熟悉，那是因爲他們還從binomial theorem，其中常見的例子有：

(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

你並不需要使用一個循環，這簡直是pascal's triangle，公式：

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

將生成您的位置（n，k）的答案。

Answer 3

試試這個：

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