Разработка алгоритма биномиального коэффициента с использованием одномерного массива

Question

Я уже разработал следующий алгоритм, определяющий биномиальный коэффициент с использованием двумерного массива. Например, для вычисления биномиального коэффициента п выбрать к, мы можем создать двумерный массив следующим образом:

int[][] arr = new int[n][k]; 

Мы можем заполнить массив следующим образом:

for(int i = 0; i <= n; i++){ 
    for(int j = 0; j <= minimum(i, k); j++){ 
     if(j == 0 || i == j){ 
     arr[i, j] = 1; 
     } else{ 
     arr[i, j] = arr[i - 1, j - 1] + arr[i - 1, j]; 
     } 
    } 
} 

Однако я необходимо перепроектировать этот алгоритм для использования одномерного массива из индексов 0-k. У меня много проблем с тем, как это сделать. Я начал с малого шага и понял некоторые общие случаи:

• Если k = 0, arr [0] будет 1, и это будет возвращено независимо от n.
• Если k = 1, arr [0] будет 1, arr [1] должен быть n, если я его проектирую в цикле.

Когда я говорю k = 2, это становится сложным, потому что значение arr [2] будет действительно зависеть от предыдущих значений. Я считаю, что, как я петлю (скажем, от i = 0 до i = n), значения arr [] будут меняться, но я не могу понять, как это сделать. Я начал с чего-то в этом направлении:

for(int i = 0; i <= n; i++){ 
    for(int j = 0; j <= minimum(i, k); j++){ 
     if(j == 0 || i == j){ 
     arr[j] = 1; 
     } else if(j == 1){ 
     arr[j] = i; 
     } else{ 
     arr[j] = ??; // I can't access previous values, because I didn't record them? 
     } 
    } 
} 

Как я должен справиться с этим?

Answer 1

Вот код, который использует только один один одномерный массив:

int[] coefficients = new int[k + 1]; 
coefficients[0] = 1; 
for (int i = 1; i <= n; i++) { 
    for (int j = k; j >= 1; j--) { 
     coefficients[j] += coefficients[j - 1]; 
    } 
} 

Почему это исправить? Чтобы вычислить coefficients[j] для фиксированного i, нам необходимо знать значение coefficients[j - 1] и coefficients[j] для i - 1. Если мы итерации от k до 0, мы можем безопасно записать новое значение для текущей позиции, потому что нам никогда не понадобится его старое значение.