leetcode 96 Unique Binary Search Trees

左子树要比根节点小,右子树要比根节点大

数组{1,2,3,4,5,6} 最大数的跟节点可能是1,2,3,4,5,6,

当是1 时, {2,3,4,5,6} 为右子树

当是2时, {1} 位左子树,{3,4,5,6}为右子树

当为3时,{1,2}为左子树,{4,5,6}为右子树

选择一个根节点时,排列的个数为左子树的排列*右子树的排列

解题:

  • 构造一个动态规划数组dp,用来存i个数时对应的排列的个数
  • 生成这个动态数组dp[i]+=dp[j]+dp[i-j-1]. j从0 到i, 对于i个数时,根节点的选择从0到i
class Solution {
public:
    int numTrees(int n) {

        vector<int> dp(n+1,0);
        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-j-1];
            }
            
        }
        return dp[n];
    }
};

  

原文地址:https://www.cnblogs.com/fanhaha/p/7351845.html