343.整数拆分

文章：8. 整数拆分

题目：343. 整数拆分

【思路】

将凑成整数的和，凑出最大的乘积。

1.确定dp[i]及其下标

dp[i] : 拆分数字i，得到的最大乘积dp[i]

2.确定递推公式

dp[i]是如何获得的？

dp[i] 可以 j *(i-j) 、dp[i-1]+1获得。

因此从二者中取最大值即可。

dp[i] = max(j*(i-j) , dp[i-j] *j)

同时，因为i和j 会变化，会重复计算dp[i]，因此我们还需要对dp[i]进行比较

-> dp[i] = max(dp[i],max(dp[i-j]*j, j * (i-j)))

3.数组初始化

dp[2] = 1

4.确定遍历顺序

因为dp[i]依靠dp[i-j]的状态，所以遍历顺序一定是从前向后的。

5.举例推导

。。。。

  • Java实现
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int integerBreak(int n) {
        int[] dp = new int[n+1];
        dp[2]=1;
        for(int i = 3;i <= n ;i++){
            for(int j = i-1 ; j >=0;j--){
                dp[i]  = Math.max(dp[i],Math.max(dp[i-j] *j , j*(i-j)));
            }
        }
        return dp[n];
    }
}
  • Go实现
1
2
3
4
5
6
7
8
9
10
func integerBreak(n int) int {
    dp:= make([]int,n+1)
    dp[2] = 1
    for i:=3;i <= n;i++{
        for j := i-1;j >=0 ;j--{
            dp[i] = max(dp[i],max(dp[i-j]*j,j*(i-j)))
        }
    }
    return dp[n]
}

96.不同的二叉搜索树

文章：9. 不同的二叉搜索树

题目：96. 不同的二叉搜索树

【思路】

dp[3]，就是元素1为头结点搜索树的数量+元素2为头结点搜索树的数量+元素3为头结点搜索树的数量。

元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量。

元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量。

元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量。

所以dp[3] = dp[2]*dp[0] + dp[1] * dp[1] + dp[0] *dp[2]

1.确定数组dp[i]及其下标的含义

dp[i] : 1到i为节点组成的二叉搜索树的个数为dp[i]（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[0] 应该是多少？

从定义上来说，空节点也是一棵二叉树，也是一棵二叉搜索树；从乘法来说也需要dp[0]为1，不然0*任何数都为0

4.确定遍历顺序

dp[i]是依靠i之前的节点数的，因此需要遍历i里面的每一个数作为头结点的状态。

5.举例推导

…

  • Java实现
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    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++){//j可以等于i
                dp[i] += dp[j-1]*dp[i-j];
            }
        }
        return dp[n];
    }
}
  • Go实现
1
2
3
4
5
6
7
8
9
10
func numTrees(n int) int {
    dp:= make([]int,n+1)
    dp[0]=1
    for i:=1;i<=n;i++{
        for j:=1;j<=i;j++{
            dp[i] += dp[j-1]*dp[i-j]
        }
    }
    return dp[n]
}

【算法总结】

  • 整数拆分：需要**将dp[i]拆成dp[i-j]*j 和 j *(i-j)取最大值，并且由于dp[i]会不断更新，因此也需要比较dp[i]和以上最大值**，取两者真正的最大值。

  • 不同的二叉搜索树：头结点为n的二叉树实质是左右子树为由前n项的二叉树累加组成，*dp[i] += dp[i-j]dp[j-1]