LeetCode 96. Unique Binary Search Trees
发布时间:2020-12-14 03:48:35 所属栏目:大数据 来源:网络整理
导读:这道题和树基本没什么关系,完全就是 Catalan Number。 给定一个数 i , 1作为根,左边有 0 个节点,右边有 i-1 个节点 2作为根,左边有 1 个节点,右边有 i-2 个节点 ... i 作为根,左边有 i-1 个节点,右边有 0 个节点 记 dp[i] 为给定 i 时的个数,dp[n]
这道题和树基本没什么关系,完全就是 Catalan Number。 给定一个数 i , 1作为根,左边有 0 个节点,右边有 i-1 个节点 2作为根,左边有 1 个节点,右边有 i-2 个节点 ... i 作为根,左边有 i-1 个节点,右边有 0 个节点 记 dp[i] 为给定 i 时的个数,dp[n] 为所求 根据上述分析,得出递推公式 dp[i] = sum_{j=0}^{i-1} dp[j] * dp[i-j-1] base case: dp[0] = 1? 因为空也算一种情况 ? class Solution { public: int numTrees(int n) { vector<int> dp(n+1); dp[0] = 1; for (int i=1;i<=n;++i){ for (int j=0;j<=i-1;++j){ dp[i] += dp[j]*dp[i-j-1]; } } return dp[n]; } }; (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |