leetcode - [96] Unique Binary Search Trees

2020/06/18

问题描述

Given n, how many structurally unique BST’s (binary search trees) that store values 1 … n?

给你一个整数n,请计算可以构成多少种唯一的BST

举个例子:

解法1

Thanks @pradosh

来看下示意图:

这道题使用DP思想,关键在于找到关系公式

如果n = 1,显然只有一种。

如果n = 2,显然有两种。

如果n = 3,这里要分成三步。

第一步,根节点为1,考虑一下左右两边各有哪些选择?

左边没有选择,而右边你有两个节点可以组合。

这就回到了n = 2,所以对于root = 1,它的数量为dp[0] * dp[2] = 1 * 2 = 2

第二步,根节点为2,左边只能放节点1,右边只能放节点3

所以,对于root = 2,它的数量是dp[1] * dp[1] = 1 * 1 = 1

第三步,以此类推。

所以我们可以推出关系公式:

dp[n] = dp[0] * dp[n-1] + dp[1] * dp[n-2] + ... dp[n-1] * dp[0]

来看下实现:

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

Enjoy it !


一位喜欢提问、尝试的程序员

(转载本站文章请注明作者和出处 姚屹晨-yaoyichen

Post Directory