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

本文主要是介绍代码随想录算法训练营第40天|● 343. 整数拆分 ● 96.不同的二叉搜索树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

 343. 整数拆分

动归 递归拆

class Solution:def integerBreak(self, n: int) -> int:dp=[0]*(n+1)dp[2]=1for 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 1if n==2:return 1if n==3:return 2return pow(3,int(n//3)-1)*4

96. 不同的二叉搜索树

究极拆分 左排列*右排列

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

这篇关于代码随想录算法训练营第40天|● 343. 整数拆分 ● 96.不同的二叉搜索树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---