My code:
public class Solution {
public int numTrees(int n) {
if (n <= 0)
return 0;
if (n == 1)
return 1;
int[] count = new int[n + 1];
count[0] = 1;
count[1] = 1;
for (int i = 2; i < n + 1; i++) {
for (int j = 0; j < i; j++)
count[i] += count[j] * count[i - j - 1];
}
return count[n];
}
}
My test result:
这次作业做的不定心，是在床上做的，然后越做越乱。。。
然后看了解答才有思路。动态规划，层层递进。
比如有4个点。那么就四种情况。
左边0个结点，右边3个。
左边1个结点，右边2个。
左边2个结点，右边1个。
左边3个结点，右边0个。
那么接下来就是求，3个结点能构造的树有几种。那么就三种情况。
左边0个结点，右边2个。
左边1个结点，右边1个。
左边2个结点，右边0个。
那么接下来就是求，2个结点能构造的树有几种。那么就两种情况。
左边0个结点，右边0个。
左边1个结点，右边1个。
然后这个思路是反着的。
所以我们倒过来，就可以一层层，从2个结点，推到3个结点，最后推到n个结点，以此迭代。
然后代码就自然的出来了，也很简单。
http://fisherlei.blogspot.com/2013/03/leetcode-unique-binary-search-trees.html
**
总结：今天一天不定心，计划的事基本没一件做完，所以觉得丹妮还是挺牛的，回去没怎么休息，就接着开始忙了。心痛，但又不得不鼓励她继续努力下去。
我们之间要说的太多了。等300天后吧。
明天去医院拿体检报告，希望一切安好。
**
Anyway, Good luck, Richardo!
My code:
public class Solution {
public int numTrees(int n) {
if (n <= 0) {
return 0;
}
int[] cache = new int[n + 1];
return helper(0, n - 1, cache);
}
private int helper(int begin, int end, int[] cache) {
if (begin >= end) {
return 1;
}
if (cache[end - begin + 1] > 0) {
return cache[end - begin + 1];
}
int sum = 0;
for (int i = begin; i <= end; i++) {
sum += helper(begin, i - 1, cache) * helper(i + 1, end, cache);
}
cache[end - begin + 1] = sum;
return sum;
}
}
是分割性DP，习惯性的写了出来。然后TLE。加了cache就行了。
然后看了 iteration DP 的方法，其实和我的差不多，虽然实现起点不同。
iteration DP reference:
https://discuss.leetcode.com/topic/8398/dp-solution-in-6-lines-with-explanation-f-i-n-g-i-1-g-n-i/2
Anyway, Good luck, Richardo! -- 08/25/2016
