阅读 4

Unique Binary Search Trees——LeetCode

题目描述

思想

这是一题动态规划题,首先很容易想到在数字为1的时候,只有一种方法可以形成二叉搜索树;再大胆假设一下,在数字为5的时候,假设{1}为根,则{2,3,4,5}为形成子二叉搜索树,与{1,2,3,4}形成的二叉搜索树的个数是一样的,所以个数为dp[4]*dp[0](假设dp[0]为1);当根为{2}的时候,二叉搜索树的个数为dp[1]*dp[3];依次类推,当根为{5}的时候,二叉搜索树的个数为dp[0]*dp[4]。

代码实现

class Solution {
    
    public int numTrees(int n) {
        
        int[] array = new int[n+1];
        array[0] = 1;
        array[1] = 1;
        for(int i = 2;i <= n; i++){
            for(int j = 0; j < i; j++){
                array[i] += array[i-j-1]*array[j];
            }
            
        }
        return array[n];
    }
}
复制代码
关注下面的标签,发现更多相似文章
评论