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

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

Пример:

Input: numPeople = 4
Output: 2

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

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

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

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

😎 Решение:

class Solution {
public:
    int numHandshakes(int numPeople) {
        int n = numPeople / 2;
        vector<int> catalan(n + 1, 0);
        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];
    }
};

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