分类
C++ Develop 算法

LeetCode题目:Unique Binary Search Trees,一维动态规划

用一维动态规划解。
Sigma(左边的子树可能状态 * 右边子树可能状态) = 当前个数的nodes形成的BST总数。



Unique Binary Search Trees
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



代码:8ms过大集合

class Solution {
public:
    int numTrees(int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(n <= 1) return n;
        //ways[i] rep. the number of ways with i nodes
        int *ways = new int[n + 1];
        ways[0] = 1;
        ways[1] = 1;
        for(int i = 2 ; i <= n; ++i) {
            ways[i] = 0;
            for(int left = 0; left < i; ++ left) {
                //with number of left noeds in the left sub-tree
                int lways = ways[left];
                int rways = ways[i - left - 1];
                ways[i] += lways * rways;
            }
        }
        int ret = ways[n];
        delete [] ways;
        return ret;
    }
};

“LeetCode题目:Unique Binary Search Trees,一维动态规划”上的6条回复

发表评论

电子邮件地址不会被公开。 必填项已用*标注