[leetcode 96]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

给定数字n ，建立一个n个节点的二叉树，其中每个节点的值为1，2，3…….n，问有多少种方法

动态规划，直接递归会超时

AC代码

class Solution {public:int numTrees(int n) {int count[n+1];memset(count,0,sizeof(count));count[0]=1;count[1]=1;int temp=0;for(int i=2;i<=n;++i){temp=i-1;for(int j=temp;j>=0;–j){count[i]+=count[temp-j]*count[j];}}return count[n];}};

版权声明：本文为博主原创文章，未经博主允许不得转载。

，如果心胸不似海，又怎能有海一样的事业。