Q16 Unique Binary Search Trees - LeetCode 96

PHOTO EMBED

Wed Mar 22 2023 17:35:40 GMT+0000 (Coordinated Universal Time)

Saved by @Ayush_dabas07

class Solution {
    public int numTrees(int n) {
        /* basically a question of catalan number , learn the first 5 catalan
        numbers to be able to find the pattern in questions
        */

        int[] dp = new int[n+1];
        dp[0] = 1 ; dp[1] = 1;
        
        
        for(int k = 2 ; k <= n ; k++){

            for(int i = 0 , j = k-1 ; i<=k-1 ; i++ , j--)
            dp[k] += dp[i] * dp[j];
        }

        return dp[n];
    }
}
content_copyCOPY

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