Задача: 1259. Handshakes That Don't Cross
Сложность: hard

Вам дан список эквивалентных пар строк synonyms, где synonyms[i] = [si, ti] означает, что si и ti являются эквивалентными строками. Вам также дан текст предложения. Верните все возможные синонимичные предложения, отсортированные лексикографически.

Пример:

Input: numPeople = 4
Output: 2

👨‍💻 Алгоритм:

1⃣Определим массив для хранения каталановых чисел.

2⃣Заполним массив каталановых чисел с помощью рекуррентной формулы.

3⃣Вернем 𝐶𝑛𝑢𝑚𝑃𝑒𝑜𝑝𝑙𝑒/2C.

😎 Решение:

public class Solution {
    public int numHandshakes(int numPeople) {
        int n = numPeople / 2;
        int[] catalan = new int[n + 1];
        catalan[0] = 1;

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                catalan[i] += catalan[j] * catalan[i - 1 - j];
            }
        }

        return catalan[n];
    }
}

Ставь 👍 и забирай 📚 Базу знаний