[프로그래머스] 올바른 괄호의 갯수

https://programmers.co.kr/learn/courses/30/lessons/12929

코딩테스트 연습 - 올바른 괄호의 갯수

 

카탈란 수로 점화식에 기반하여 동적 계획 알고리즘으로 풀었다.

 

C0 = 1

Cn+1 = C0*Cn + C1*Cn-1 + C2*Cn-2 + ... + Cn*C0

 

answer = Cn

 

class Solution {
    public int solution(int n) {
        int answer = 0;
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        
        for (int i=2;i<n+1;i++) {
            for (int j=0;j<i;j++) {
                dp[i] += (dp[j] * dp[i-j-1]);
            }
        }
        
        answer = dp[n];
        
        return answer;
    }
}