代码随想录算法训练营第41天|● 343. 整数拆分 ● 96.不同的二叉搜索树

343. 整数拆分

已解答
中等
相关标签
相关企业
提示
给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。
返回 你可以获得的最大乘积 。

示例 1:
输入: n = 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。
示例 2:
输入: n = 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

提示:

• 2 <= n <= 58

代码

func integerBreak(n int) int {
    //dp[i] 表示当和为i时的最大乘积
    dp := make([]int, n+1)

    dp[0] = 1
    dp[1] = 1
    // 把i 拆成 j,i-j
    for i := 2; i < n+1; i++ {
        dp[i] = dp[i-1]
        for j := 1; j < i; j++ {
            dp[i] = integerBreak_max(dp[i], integerBreak_max(dp[j], j)*integerBreak_max(dp[i-j], i-j))
        }
    }
    fmt.Println(dp)
    return dp[n]
}

func integerBreak_max(i int, i2 int) int {
    if i > i2 {
        return i
    }
    return i2
}

96. 不同的二叉搜索树

中等
相关标签
相关企业
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

示例 1：
[图片]
输入：n = 3
输出：5
示例 2：
输入：n = 1
输出：1

提示：

• 1 <= n <= 19

思路

• dp[3]，就是 元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量
  • 元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量
  • 元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量
  • 元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量
  • 有2个元素的搜索树数量就是dp[2]。
  • 有1个元素的搜索树数量就是dp[1]。
  • 有0个元素的搜索树数量就是dp[0]。
• 所以dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]
• 递推公式：dp[i] += dp[j - 1] * dp[i - j]