343. 整数拆分

https://leetcode.cn/problems/integer-break/
这个方法还是蛮好想的，自己计算一些就可以知道规律。

class Solution {public int integerBreak(int n) {int[] dp =new int[n];dp[0]=1;dp[1]=1;int max;for(int j=2;j<n;j++){max=1;for(int i=1;i<=(j+1)/2;i++){max=Math.max(max,Math.max(dp[i-1],i)*Math.max(dp[j-i],(j+1-i)));}dp[j]=max;}return dp[n-1];}
}

看了讲解后简化了一下，数组初试就是有值的。

class Solution {public int integerBreak(int n) {int[] dp =new int[n];dp[0]=1;dp[1]=1;for(int j=2;j<n;j++){for(int i=1;i<=(j+1)/2;i++){dp[j]=Math.max(dp[j],Math.max(dp[i-1],i)*Math.max(dp[j-i],(j+1-i)));}}return dp[n-1];}
}

96. 不同的二叉搜索树

https://leetcode.cn/problems/unique-binary-search-trees/
这个没有找出规律。
看了讲解：
dp[3]，就是 元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量
元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量
元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量
元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量

class Solution {public int numTrees(int n) {int[] dp=new int[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[j]*dp[i-1-j];}}return dp[n];}
}