day41| 342+96

cp1999 / 2023-05-05 / 原文

343. 整数拆分

题目简述：

给定一个正整数 n ，将其拆分为 k 个正整数的和（ k >= 2 ），并使这些整数的乘积最大化。

返回 你可以获得的最大乘积 。

思路：

1. 当n>2时，正整数n可以被拆分成至少两个正整数的和。

2. 令x是拆分出来的第一个整数，则剩余部分n-x可以不拆分，也可以继续成两个正整数的和

3. 利用动态规划来求解

4. 递推公式，当i>2，假设对正整数i拆分出的第一个正整数是j，则可以以下两种情况：

　　1）将 i 拆分成 j 和 i-j，且 i-j 不拆分，此时乘积为 j*（i-j）

　　2）将 i 拆分成 j 和 i-j，且 i-j 继续拆分，则此时乘积为 j*dp[i-j]

　　　每个正整数拆分后对应的最大乘积可以由比其小的正整数拆分后的最大乘积推出，于是可以用动态规划

　　3）当 j 固定，dp[i] = max(j*(i-j), j*dp[i-j])

　　4）当 j 不固定，那么需要遍历 j 再求max

代码如下：

class Solution:
    def integerBreak(self, n: int) -> int:
        dp = [0] * (n + 1)
        for i in range(2, n + 1):
            for j in range(i):
                dp[i] = max(dp[i], j * (i - j), j * dp[i - j])
        return dp[n]

也可以数学法求解

class Solution:
    def integerBreak(self, n: int) -> int:
        two_num=n%3
        three_num=n//3
        if n==2:
            return 1
        if n==3:
            return 2

        if two_num==1:
            a=3**(three_num-1)
            b=2**(two_num)
            result=a*b*b
        elif two_num==2:
            a=3**(three_num)
            result=2*a
        else:
            a=3**(three_num)
            result=a
        return result

96. 不同的二叉搜索树

题目简述：

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

思路：

1. 对于一个n

2. 取其中的k作为头结点，那么前面有k-1个数，后面有n-k个数

3. 种数=前面k-1个数组合的种数+后面n-k个数组合的种树

4. 对所有的k求和，就是1到n互不相同的二叉搜索树的种数

代码如下：

class Solution(object):
    def numTrees(self, n):
        dp=[0 for _ in range(n+1)]
        dp[0]=1
        dp[1]=1

        for i in range(2,n+1):
            for j in range(1,i+1):
                dp[i]+=dp[j-1]*dp[i-j]
        
        return dp[n]