f*********m
发帖数: 726 | 1 leetcode 上的Unique Binary Search Trees,算总的Binary Search Trees数目：
Given n, how many structurally unique BST's (binary search trees) that store
values 1...n?
可以用dp:
int dp[n+1];
memset(dp, 0, (n+1)*sizeof(int));
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];
若是要算总的Trees数目，那应该是
dp[i] += 2*dp[j]*dp[i-j-1]吧？
既一个节点既可以出现在根的左边，又可以出现在右边？ |
j*****y
发帖数: 1071 | 2 应该不需要，已经包含了。
store
【在 f*********m 的大作中提到】
: leetcode 上的Unique Binary Search Trees,算总的Binary Search Trees数目：
: Given n, how many structurally unique BST's (binary search trees) that store
: values 1...n?
: 可以用dp:
: int dp[n+1];
: memset(dp, 0, (n+1)*sizeof(int));
: dp[0] = 1;
: dp[1] = 1;
:
: for (int i = 2; i <= n; i++) {
|
d*********g
发帖数: 154 | 3
怎么包含了呢？求指点
【在 j*****y 的大作中提到】
: 应该不需要，已经包含了。
:
: store
|
j*****y
发帖数: 1071 | 4 比如 1 * 4 + 2 * 3 + 3 * 2 + 4 * 1
这里面已经包含了重复了
【在 d*********g 的大作中提到】
:
: 怎么包含了呢？求指点
|
f*********m
发帖数: 726 | 5 我觉得没有包含。BST对于节点的顺序有限制，比如BST：1为根，2作为子节点只能在1
右侧。在这种情况下只能有1个bst.
而任意的tree没有这个限制。2可以是1的左或右子节点。所以可以有两个tree.
你的例子中，比如1 * 4 + 4 * 1，第一项是说以1为根，第二项是说以4为根。所以其
实没有包含重复。
【在 j*****y 的大作中提到】
: 比如 1 * 4 + 2 * 3 + 3 * 2 + 4 * 1
: 这里面已经包含了重复了
|
j*****y
发帖数: 1071 | 6 这个题目是 BST
1
【在 f*********m 的大作中提到】
: 我觉得没有包含。BST对于节点的顺序有限制，比如BST：1为根，2作为子节点只能在1
: 右侧。在这种情况下只能有1个bst.
: 而任意的tree没有这个限制。2可以是1的左或右子节点。所以可以有两个tree.
: 你的例子中，比如1 * 4 + 4 * 1，第一项是说以1为根，第二项是说以4为根。所以其
: 实没有包含重复。
|
f*********m
发帖数: 726 | 7 我知道。我问的是这个题目的扩展，即,不是要生成bst而是要生成任意tree.
【在 j*****y 的大作中提到】
: 这个题目是 BST
:
: 1
|
f*********m
发帖数: 726 | |
