343.整数拆分
给定一个正整数 n
,将其拆分为 k
个 正整数 的和( k >= 2
),并使这些整数的乘积最大化。
返回 你可以获得的最大乘积 。
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], j * (i - j), j * dp[i - j])
return dp[n]
96.不同的二叉搜索树
给你一个整数 n
,求恰由 n
个节点组成且节点值从 1
到 n
互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。
class Solution:
def numTrees(self, n: int) -> int:
# dp[i]用来保存当结点个数为i时的种树
dp = [0] * (n + 1)
# 空结点也算一种情况
dp[0] = 1
# 逐渐增加结点个数
for i in range(1, n + 1):
# 划分左右子树,总数不能超过i
for j in range(1, i + 1):
dp[i] += dp[j - 1] * dp[i - j]
return dp[n]