题目：343. 整数拆分
思路：
状态转移方程：dp[i] = max(dp[i], max((i-j)*j,dp[i-j]*j))，其中(i-j)*j是把i分成了两个数，dp[i-j]*j是把(i-j)分成了两个数及以上(也就是说这个式子代表3个数及以上)。因为dp是状态转移，是前面数的最优解，所以不需要考虑到底分成了几个数。
其实只有前面几个是走了(i-j)*j，后面的式子全部都是走的dp[i-j]*j
代码：
func integerBreak(n int) int {
dp := make([]int, n+1)
dp[2] = 1 // 2只能分成1、1结果是 1 * 1 = 1
for i:=3; i<=n;i++ {
for j:=1; j<=i/2; j++ { // 当然可以直接<=i-1，这样写可以优化一点(靠近中间更大)
dp[i] = max(dp[i], max((i-j)*j,dp[i-j]*j))
}
}
return dp[n]
}
func max(a,b int) int {
if a > b {
return a
}
return b
}
参考：
题目：96. 不同的二叉搜索树
思路：
重点不是节点数，而是节点的布局，这道题就算没有数也无所谓，直接问最多有多少种布局：
以3(i)个节点为例：
- 左0右2 (0 i-1)
- 左1右1 (1 i-2)
- 左2右0 (2 i-3)
即dp[3] = dp[0]*dp[2] + dp[1]*dp[1] + dp[2]*dp[0]
代码：
func numTrees(n int) int {
dp := make([]int, n+1)
dp[0] = 1
for i := 1; i <= n; i++ {
for j := 0; j < i; j++ {
dp[i] += dp[i-j-1] * dp[j]
}
}
return dp[n]
}