整数拆分
题目：
给定⼀个正整数 n，将其拆分为⾄少两个正整数的和，并使这些整数的乘积最⼤化。 返回你可以获得的最⼤乘积。
示例 1:
输⼊: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:
输⼊: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。
提示:
- 2 <= n <= 58
说明: 你可以假设 n 不⼩于 2 且不⼤于 58。
动态规划五部曲：
- 1使用一个一维（二维）dp数组来保存递归结果：
由于我们要求的是对任意的整数n找到其规定条件下的最大乘积，所以首先想到：
状态转移方程dp[i]表示数字i的最大乘积
- 2.确定递推公式
要找到dp[i]的最大乘积，可以将dp[i]划分为一个不会再被划分的数j，和一个会被划分m次但是总和为 （i-j）的数.
此时由于j不会再被划分，所以要使dp[i]最大，则 就要对（i-j）进行拆分使得拆分后的几个整数的乘积最大，即dp[i-j]。
所以
dp[i]的最大乘积=j * dp[i-j]
由于j是一个不确定的数，所以需要对j进行遍历,确定j为某个值时使得j*dp[i-j]最大
上面我们就解释了为什么dp[i]=j*dp[i-j],但是有一个容易被忽略的问题：
题目我们的dp[i]是由至少两个整数相乘得到的。那么同样的dp[i-j]也是由至少两个整数组成的。所以这里遗漏了一种情况：若是i-j不进行划分时得到dp[i]的最大值，那么dp[i]=j*(i-j)
综上所诉，我们的递推公式应该是dp[i]=max( j * dp[i-j], j*(i-j) )
- 3.Dp数组如何初始化
由于题目中最小的能够进行划分的数是2,所以严格的定义来说，我们只需要从2开始初始化递推函数：dp[2]=1; (1*1=1)
但此时要注意，递推公式dp[i]=j*dp[i-j]中的i-j要保证大于等于2
- 4.确定遍历序列（eg:不同路径）
从递推公式dp[i]=j*dp[i-j]可以看出后面的结果是由前面i-j推导出来的，所以i⼀定是从小到大遍历，先有dp[i - j]再有dp[i]
- 5.举例推导递推公式，避免错误
class Solution {
public:int integerBreak(int n) {vector<int>dp(n+1,0);dp[2]=1;for(int i=3;i<=n;i++){//dp[i]中的ifor(int j=1;j<=i-2;j++){//要保证dp[i-j]中的i-j>=2int t=max(j*dp[i-j], j*(i-j));if(t>dp[i])dp[i]=t;}}return dp[n];}
};96不同的二叉搜索树
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
示例 1：
输入：n = 3 输出：5
示例 2：
输入：n = 1 输出：1
提示：
1 <= n <= 19
对于任意一个节点，它的组成是根节点，左孩子和右孩子。当一共有三个节点时，忽略节点的值，它可能的布局是：(2^0)表示最孩子两个节点，右孩子0个节点，必然有一个节点作为根节点
(2^0)，（0^2）(1^1),三种可能存在的节点排序，而对于右两个节点的分支又可以有（0^1）(1^0)两个排序结构，所以有三个节点时可能存在的不同结构有2+1+2=5种
相当于有n个节点就把n进行拆分，一个作为根节点，剩余的n-1个根据结构放在左右子树上，此时就可以将情况划分为左子树有j个节点，则右子树有（n-1-j）个节点，则有递推公式dp[n]=dp[j]*[n-1-j],由于j个个数可以改变，所以j进行遍历，从0~n-1 。
1. 确定dp数组（dp table）以及下标的含义
dp[i] ： 1到i为节点组成的⼆叉搜索树的个数为dp[i]。
2. 确定递推公式
在上⾯的分析中，其实已经看出其递推关系， dp[i] += dp[以j为头结点左⼦树节点数量] * dp[以j为头结点右⼦树节
点数量]
j相当于是头结点的元素，从1遍历到i为⽌。
所以递推公式：dp[i] += dp[j - 1] * dp[i - j]; ，j-1 为j为头结点左⼦树节点数量，i-j 为以j为头结点右⼦树节点数量
3. dp数组如何初始化
初始化，只需要初始化dp[0]就可以了，推导的基础，都是dp[0]。
那么dp[0]应该是多少呢？
从定义上来讲，空节点也是⼀棵⼆叉树，也是⼀棵⼆叉搜索树。
从递归公式上来讲，dp[以j为头结点左⼦树节点数量] * dp[以j为头结点右⼦树节点数量] 中以j为头结点左⼦树节点
数量为0，也需要dp[以j为头结点左⼦树节点数量] = 1， 否则乘法的结果就都变成0了。
所以初始化dp[0] = 1
4. 确定遍历顺序
⾸先⼀定是遍历节点数，从递归公式：dp[i] += dp[j - 1] * dp[i - j]可以看出，节点数为i的状态是依靠 i之前节点数
的状态。
5：举例推导递推公式，避免错误
class Solution {
public:int numTrees(int n) {vector<int>dp(n+1,0);dp[0]=1;dp[1]=1;for(int i=2;i<=n;i++){for(int j=0;j<=i-1;j++){dp[i]+=dp[j]*dp[i-1-j];}}return dp[n];}
};
