96. Unique Binary Search Trees

문제

https://leetcode.com/problems/unique-binary-search-trees/

내 코드

import java.util.*;

class Solution {
    int dp[];
    public int numTrees(int n) {
        dp = new int[20];
        for(int i=0; i<dp.length; i++)
            dp[i] = -1;
        dp[0] = 1; dp[1] = 1;
        return dfs(n);
    }

    int dfs(int n){
        if(dp[n] != -1)
            return dp[n];        
        dp[n] = 0;
        for(int i=0; i<n; i++)
            dp[n] += (dfs(i)*dfs(n-1-i));
        return dp[n];
    }

}

피드백

• 보자마자 dp 문제인거 같았음
• 어떻게 바로 dp로 할지는 모르겠고, 일단 dfs식이 떠올라서 코딩
• 코딩하고 나니 중복되는 부분을 memoization으로 처리할 수 있었음
• 시간복잡도는 다음과 같다 : https://leetcode.com/problems/unique-binary-search-trees/discuss/1565543/C%2B%2BPython-5-Easy-Solutions-w-Explanation-or-Optimization-from-Brute-Force-to-DP-to-Catalan-O(N)
  • 이번 문제는 시간 복잡도를 생각하기가 좀 어려웠다 1회독 했지만 다시 봐야 될지도 모르겠다.