343. 整数拆分
这道题感觉是融合了贪心算法和动态规划。我自己想了一早上也没想出来该怎么写，看了Carl的解题思路也没自己写出来。但现在是懂了。
这道题其实就是把n拆分成小份，算每个小份的最大值是多少。这个概念好理解，但是如何将这个概念用程序表示出来很难，需要用双层for loop去做。第一层，也就是i，它是首先从数值3开始，把从n若是等于3时的结果算出来，记录到dp数组了。然后再算n等于4…一直到等于目标值。然后里面一层的for loop，是将i拆分成各种组合，然后看哪个组合的结果是最大的。这也就是为什么j要从1开始，因为它的目的是拆分，拆分就得从最小的整数开始。而i从3开始，是因为我们一开始就把n等于0 1 2 时候的值确定了。
max(dp[i],max(j(i-j),jdp[i-j]))看起来不太简洁，它其实的意思就是max(dp[i],j(i-j),jdp[i-j])，也就是说去这三个值的最大值：当前已有的dp[i]、目前切分j和余数相乘、目前切分数和余数的最大乘积。
class Solution {
public:
int integerBreak(int n) {
vector<int> dp(n+1);
dp[0] = 0;
dp[1] = 0;
dp[2] = 1;
for(int i=3; i<=n; i++){
for(int j=1; j<i; j++){
///dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
dp[i] = max(dp[i],max(j*(i-j),j*dp[i-j]));
}
}
return dp[n];
}
};
这道题不光是我做了，俊淑也在一旁自己研究了好久，她实践很多自己办法。她的热情也带动了我好好刷题。
96.不同的二叉搜索树
根据Carl的讲解，我自己独立把学到的方法实现了。虽然中间错了很多，很多变量由于我对思路还捋得不是很清晰，所以有的值的极限设错了，比如说j的最大值应该不超过i，而不是n。
另外这道题最重要的是推导的部分。
- 首先是要理解动态规划的dp数组在这道题中是记录什么的，然后如何利用这个dp数组。
- 其次，要想明白搜索二叉树的特性，以及如何把dp数组里的值从小的二叉树融合到更大的二叉树里。要想明白：刨去根节点，左子树的点的数量乘右子树点的数量，得出来的就是在左右特定点的个数下可组成的组合数。然后把左子树从0到n-1,右子树从n-1到0，这些所有组合加到一起，就是n个数能组成的组合数。
而且这题有个陷阱，是我开始的时候忽略掉的：要记得减去根节点，也就是n-1。
class Solution {
public:
int numTrees(int n) {
vector<int> dp(n+1);
dp[0] = 1;
dp[1] = 1;
for(int i=2; i<=n; i++){
for(int j=0; j<i; j++){
dp[i] = dp[i] + dp[j] * dp[i-j-1];
}
}
return dp[n];
}
};
