Java Combinatorics с использованием Memoization / динамического программирования

Question

Я делаю программу, которая дает количество возможных комбинаций для двух чисел, например, N выбирает K. У меня есть рекурсивное решение, которое выглядит следующим образом:

public static int combinations(int group, int members) {
    if (members == 1) {
        return group;
    }
    else if (members == group) {
        return 1;
    }
    else {
        return(combinations(group - 1, members - 1) + 
                combinations(group - 1, members));
    }
}

Это работает, но мне нужно использовать запоминание, чтобы улучшить сложность времени и ускорить его для больших чисел, и я не знаю, как это сделать. Как бы я поступил так?

Answer 1

Одним из способов является кэширование, которое идет с большой ценой использования памяти.

public static int combinations(int group, int members) {
    if (members > group - members) {
        members = group - members; // 21 choose 17 is same as 21 choose 4
    }

    final int[][] cache = new int[group][members];
    return combinations(group, members, cache);
}
private static int combinations(int group, int members, int[][] cache) {
    if (cache[group - 1][members - 1] > 0) {
        return cache[group - 1][members - 1];
    }
    else if (members == 1) {
        cache[group - 1][members - 1] = group;
        return group;
    }
    else if (members == group) {
        cache[group - 1][members - 1] = 1;
        return 1;
    }
    else {
        return (combinations(group - 1, members - 1, cache) + combinations(group - 1, members, cache));
    }
}

Я провел небольшой тест (непрофессиональные тесты) и обнаружил, что оригинальный метод занимает половину времени метода кэширования. Похоже, что все эти операции чтения / записи в кэш массива резко замедляют процесс.

Другой способ - изменить всю формулу.

public static int combinations(int group, int members) {
    if (members > group - members) {
        members = group - members;
    }

    int answer = 1;
    for (int i = group; i > group - members; i--) {
        answer *= i;
    }

    for (int i = 1; i <= members; i++) {
        answer /= i;
    }

    return answer;
}

Опять же, я протестировал новый метод с оригинальным (который я заставил их использовать BigInteger для теста), и новый метод невероятно быстрее (26 секунд для оригинального метода против 0,00 секунд для последнего для 35 выберите 15 ).

Чтобы добавить немного, я думаю, что сложность времени для использования рекурсивного вызова составляет O((group)(log members)), тогда как использование новой формулы просто O(members).

Answer 2

По формуле n choose k = ( n - 1 choose k - 1) + ( n-1 choose k ) Подход динамического программирования снизу вверх:

dp[n][k] = dp[n-1][k-1] + dp[n-1][k] if n > k 
else if n == k
dp[n][k] = 1
else
dp[n][k] = 0

начать с n = 1 и k = 1

dp[1][1] = 1; dp[1][0] = 1; 

и затем заполните двумерный массив до dp[n][k]

Это также может быть сделано с напоминанием, как в вашем случае. Ваш метод может быть изменен на:

int[][] dp = new int[group][members];

public static int combinations(int group, int members, int[][] dp ) {

    if (members == 1) {
        return group;
    } else if (members == group) {
        return 1;
    }

    if ( dp[group][members] != 0 ) {
       return dp[group][members];
    }

    int first = 0, second = 0;
    if ( members <= group - 1) {
      first = combinations( group - 1, members - 1, dp );
      second = combinations( group - 1, members );
    } else if ( members - 1 <= group - 1 ) {
      first = combinations( group - 1, members - 1, dp );
    }
    dp[group][members] = first + second;

    return dp[group][members];
}