整数拆分
力扣题目链接
分析：
尽量将数拆成相等的数，乘积最大。
- dp数组含义：dp[i]：分拆数字i的最大乘积
- 递推公式：
dp[i] 两种拆法求得最大值：
- 拆两个，j * (i - j) 直接相乘
- 拆多个，j*dp[i-j]
- 初始化
只需要初始化 dp[2] = 1。因为dp[0] dp[1]根据dp数组含义，无意义 - 遍历顺序
顺序
var integerBreak = function(n) {
let dp = new Array(n + 1).fill(0)
dp[2] = 1
for(let i=3;i<=n;i++){
for(let j=1;j<=i;j++){
dp[i]=Math.max(dp[i],j*dp[i-j],(i-j)*j)
}
}
return dp[n]
};
优化：
j 遍历，只需要遍历到 n/2 就可以，后面就没有必要遍历了，因为拆出相似的数得到最大值。
不同的二叉搜索树
力扣题目链接
分析：
- dp数组含义
dp[i] ： 1到i为节点组成的二叉搜索树的个数。 - 递推公式
dp[i] += dp[j - 1] * dp[i - j]; ，j-1 为j为头结点左子树节点数量，i-j 为以j为头结点右子树节点数量（注意：一共i个节点，对于根节点j时,左子树的节点个数为j-1，右子树的节点个数为i-j） - 初始化
dp[0] = 1
否则，若为0，dp[1]结果为0了 - 遍历顺序
顺序。
每个节点的状态依赖前面的节点
var numTrees = function(n) {
let dp = new Array(n+1).fill(0);
dp[0] = 1;
for(let i=1;i<=n;i++){
for(let j=1;j<=i;j++){
dp[i] +=dp[j-1]*dp[i-j]
}
}
return dp[n]
};
