仅为个人记录复盘学习历程，解题思路来自代码随想录
代码随想录刷题笔记总结网址:
代码随想录
343. 整数拆分
给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
关键思路：
动规五部曲：
1.dp数组和下标的含义
dp[i]表示正数i可获得的最大乘积。
2.递推公式
dp[i]=max(i*(i-j),i*dp[i-j])
i*(i-j)代表将i拆分成两个数字，
i*dp[i-j]代表将i拆分成两个以上数字
3.数组初始化
讨论dp[0],dp[1]没有意义，dp[2]=1*1=1
4.确定遍历顺序
外层遍历，
for(int i=3;i<=n;i++)；
由于初始化从2开始，所以i从3开始；
计算dp[n]不可避免的用到dp[n-1].
内层遍历，
for(int j=1;j<=i-j;j++);
由于题目说n是一个正整数，所以对n的拆分从1开始，
j<=i-j是因为当j>i-j时，i*(i-j)会导致重复
5.举例推导
略。
代码大致如下：
public int integerBreak(int n) {//初始化int[] dp=new int[n+1];dp[2]=1;//1+1=2;1*1=1//求n的最大乘积需要求n-1的最大乘积for(int i=1;i<=n;i++){//求具体的最大乘积//j从1开始，从0开始则说明从0开始拆分，没意义//j<=i-j，因为j*（i-j）,j>i-j重复没有意义for(int j=1;j<=i-j;j++){dp[i]=Math.max(dp[i],Math.max(j*(i-j),j*dp[i-j]));}}return dp[n];}96.不同的二叉搜索树
给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种
关键思路：
动规五部曲：
1.dp数组和下标的含义
dp[i]表示1-i作为节点可以构成二叉搜索树的个数。
2.递推公式
dp[i]+=dp[j-1]*dp[i-j];
dp[j-1]代表以j为节点左子树的种数，
dp[i-j]代表以j为节点右子树的种数
3.数组初始化
dp[0]=1,dp[1]=1,dp[2]=2
4.确定遍历顺序
外层，
for(int i=1;i<=n;i++)
题中所给1-n个节点构成的树，计算dp[n]需要dp[n-1]
内层，
for(int j=1;j<=i;j++)
遍历所有可能的情况
5.举例推导
略。
代码大致如下：
public int numTrees(int n) {//初始化int[] dp=new int[n+1];dp[0]=1;//for(int i=1;i<=n;i++){for(int j=1;j<=i;j++){dp[i]+=dp[j-1]*dp[i-j];}}return dp[n];}
