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

By | 2012 年 11 月 1 日

用一维动态规划解。
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;
    }
};

6 thoughts on “LeetCode题目:Unique Binary Search Trees,一维动态规划

      1. uniEagle Post author

        that’s much safer, but not needed in this situation, because ways is a local variable, and the next line after

        delete [] ways;

        is return.

        Reply
  1. Jerry

    Great post! Not familiar with C++ semantics, but should it be “delete[] ways” instead of “delete ways”?

    Reply

发表评论

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