思路：其实本题的难点就在于如何进行遍历和递推公式应该如果推导，通过提示的用例我们可以发现有的n拆分后需要有两个数相乘，有的n拆分后需要有3个n甚至更多个n相乘，那么作为一道动态规划的题目，很明显我们应该设置dp[i]为i拆分后的最大乘积，那么我们就应该找到dp[i]的上一个状态是什么，如果我们要把一个数i拆分成两部分计算最大乘积，那么我们设其中一个数为j，那么另一个数就为i-j.乘积就为i（i-j）
那么在本题中也是同理，dp[i]可以有多个拆分部分组成，我们可以把多个部分看成两个部分来处理，设其中一个数为j，剩下的所有部分为dp[i-j]，其中dp[i-j]表示其他部分相乘的最大值，我们在双重遍历中不断计算和判断 jdp[i-j]和j*(i-j)的大小，最终得到结果dp[n]就是题目所求的值
class Solution {
public int integerBreak(int n) {
// 创建dp数组
int[] dp = new int[n+1];
// dp数组的初始化
// dp[0]和dp[1]都是无意义的 因为无法拆分 直接从2开始
dp[2] = 1;
// 遍历dp数组
for (int i = 3; i <= n;i++){
for (int j = 1; j <= i-j; j++){
// 递推公式 dp[i-j]表示可能有多个数相乘得到的结果 (i-j)则是单独的一个数
//dp[i]在这里起到更新最大值的作用
dp[i] = Math.max(dp[i],Math.max(j*(i-j),j*dp[i-j]));
}
}
return dp[n];
}
}
思路：本题关键在于递推关系的推导，手动模拟最初的几种情况之后，我们可以发现例子dp[3]中 dp[3]等于元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量。则拓展到dp[i]中对于第i个节点，需要考虑1作为根节点直到i作为根节点的所有搜索树的累加和，所有我们可以用小于i的j来进行遍历，计算dp[j]的值，再进行累加得到dp[i]
class Solution {
public int numTrees(int n) {
int[] dp = new int[n+1];
// 空树
dp[0] = 1;
// //对于第i个节点，需要考虑1作为根节点直到i作为根节点的情况，所以需要累加
for (int i = 1; i <= n;i++){
// 用j来表示 小于i的元素作为节点的情况
for (int j = 1;j <=i; j++){
// 对于根节点j
// dp[j-1] 代表左子树的搜索树数量
// dp[i-j] 代表右子树的搜索树数量
// dp[j - 1] * dp[i-j]表示单个元素为头节点时构成的搜索树数量
dp[i] += dp[j - 1] * dp[i-j];
}
}
return dp[n];
}
}
