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

admin2024-05-15  0

 343. 整数拆分

动归 递归拆

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

公式:全拆3,剩1个4

class Solution:
    def integerBreak(self, n: int) -> int:
        if n==1:return 1
        if n==2:return 1
        if n==3:return 2
        return pow(3,int(n//3)-1)*4

96. 不同的二叉搜索树

究极拆分 左排列*右排列

class Solution:
    def numTrees(self, n: int) -> int:
        dp=[0]*(n+1)
        dp[0]=1
        for i in range(1,n+1):
            for j in range(1,i+1):
                dp[i]+=dp[j-1]*dp[i-j]
        return dp[n]
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明原文出处。如若内容造成侵权/违法违规/事实不符,请联系SD编程学习网:675289112@qq.com进行投诉反馈,一经查实,立即删除!