algorithm
카탈로니아 어 숫자 알고리즘

카탈로니아 어 수 알고리즘 기본 정보

카탈로니아 어 숫자 알고리즘은 동적 프로그래밍 알고리즘입니다.

조합 수학에서 카탈로니아 어 수 는 다양한 계산 문제에서 발생하는 자연 수열의 시퀀스를 형성하며 종종 재귀 적으로 정의 된 개체가 포함됩니다. 음수가 아닌 정수 n에있는 카탈로니아 어 숫자는 '다른 방향을 개별적으로 계산하면 정규 n-gon을 n-2 삼각형으로 몇 가지 방법으로 분할 할 수 있습니까?'라는 트리 열거 형 문제에서 발생하는 숫자 집합입니다.

카탈로니아 어 수치 알고리즘의 응용 :

1. 아래쪽 열에 동전을 쌓을 수있는 방법의 수는 동전을 n 개의 연속 동전으로 구성하여 하단 동전의 양면에 동전을 넣지 않고 모든 추가 동전을 두 개의 다른 동전 위에 올려 놓아야합니다. n 번째 카탈로니아 어 번호.
2. n 개의 쌍의 괄호를 그룹화하는 방법의 수는 각 열린 괄호가 일치하는 닫힌 괄호를 갖도록 n 번째 카탈로니아 번호입니다.
3. 교차점이 아닌 직선으로 꼭지점을 연결하여 비행기의 n + 2면 볼록 다각형을 삼각형으로 자르는 방법은 n 번째 카탈로니아 어 수입니다. 오일러가 관심을 보인 어플리케이션입니다.

0부터 시작하는 번호 매기기를 사용하여 n 번째 카탈로니아 번호는 다음 방정식에 따라 이항 계수로 직접 표시됩니다.

카탈로니아 어 번호의 예 :

여기서 n = 4의 값입니다. (가장 좋은 예 - Wikipedia에서)

보조 공간 : O(n)
시간 복잡도 : O(n^2)

C # 구현

public class CatalanNumber
{
    public static int Main(int number)
    {
        int result = 0;
        if (number <= 1) return 1;
        for (int i = 0; i < number; i++)
        {
            result += Main(i)*Main(number - i - 1);
        }
        return result;
    }
}