LeetCode-96-Unique Binary Search Trees
发布时间:2020-12-14 04:26:19 所属栏目:大数据 来源:网络整理
导读:算法描述: 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 解题思路:动态规划,f(n) = f(0)*f(n-1) +??f(1)*f(n-2) +?f(2)*f(n-3)?+ f(3)*f(n-4) + f(4)*f(n-5) ......?f(n-1)*f(0) int numTrees(int n) { vector<int> dp(n+1,0); dp[0] =1; for(int i = 1; i <= n; i++){ for(int j=0; j < i; j++){ dp[i] += dp[j]*dp[i-j-1]; } } return dp[n]; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |