96. Unique Binary Search Trees
发布时间:2020-12-14 04:48:16 所属栏目:大数据 来源:网络整理
导读:问题描述: Given? n ,how many structurally unique?BST‘s?(binary search trees) that store values 1 ...? n ? Example: Input: 3Output: 5Explanation: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
问题描述: Given?n,how many structurally unique?BST‘s?(binary search trees) that store values 1 ...?n? Example: Input: 3 Output: 5 Explanation: 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个数字,每一个数字都可能是根节点,从中抽取? ?1?≤ i?≤ n 可以抽象出一棵树: ? 左子树为由 [1,i-1]构成的树,有i-1个节点 右子树为由[i+1,n]构成的树,有n-i个节点 所以状态转移方程为: dp[i] =?Σ(dp[k] * dp[i-k-1])??1?≤ k ≤ 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 k = 0; k < i; k++){ dp[i] += dp[k] * dp[i - k - 1]; } } return dp[n]; } }; (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |