星空网 > 软件开发 > Java

LeeCode

题目:

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

For example,
Given n = 3, there are a total of 5 unique BST's.

  1     3   3   2   1  \    /   /   / \   \   3   2   1   1  3   2  /   /    \         \  2   1     2         3

思路:

找规律

1. 没有节点,BST (Binary Search Tree)为1个, 即空树

2. 有一个节点,BST为1个,即自身为根节点

3. 有二个节点,BST为2个,1为root,左为空,右为2;2为root,左为1,右为空,其实就是dp[0]*dp[1] + dp[1]*dp[0]

      1                  2

        \               /

         2            1

4. 有三个节点

 1               1                  2                       3             3  \                \               /    \                  /              /   3               2              1       3             2             1 /                   \                                  /                 \
2                      3                               1                    2

可以推出dp[3] = dp[0]*dp[2] + dp[1]*dp[1] + dp[2]*dp[0]

package bst;public class UniqueBinarySearchTrees {  public int numTrees(int n) {    int[] dp = new int[n + 1];    dp[0] = 1;    dp[1] = 1;    for (int i = 2; i <= n; ++i) {      for (int j = 0; j < i; ++j) {        dp[i] += dp[j] * dp[i - 1 - j];      }    }    return dp[n];  }    public static void main(String[] args) {    // TODO Auto-generated method stub    UniqueBinarySearchTrees u = new UniqueBinarySearchTrees();    System.out.println(u.numTrees(3));  }}

 




原标题:LeeCode

关键词:

*特别声明:以上内容来自于网络收集,著作权属原作者所有,如有侵权,请联系我们: admin#shaoqun.com (#换成@)。

中东电商物流:https://www.goluckyvip.com/tag/11370.html
包裹配送:https://www.goluckyvip.com/tag/11371.html
法国税局:https://www.goluckyvip.com/tag/11373.html
站内秒杀:https://www.goluckyvip.com/tag/11375.html
怎么回事:https://www.goluckyvip.com/tag/11376.html
奥运会:https://www.goluckyvip.com/tag/11377.html
价格翻了8倍,居然还有人买,秘诀在这里。:https://www.kjdsnews.com/a/1836642.html
欧洲B2B电商市场有待挖掘!销售总额将达1.7万亿欧元:https://www.kjdsnews.com/a/1836643.html
相关文章
我的浏览记录
最新相关资讯
海外公司注册 | 跨境电商服务平台 | 深圳旅行社 | 东南亚物流