【代码随想录算法训练营】第41天 | 第九章 动态规划（三）+ 复习第11天 第五章 栈与队列（一）

主要内容

动态规划题目

343. 整数拆分

思路分析

难点递推公式
dp[i]表示将i进行分解得到的最大乘积
递归公式 dp[i] = max(j*(i-j), j*dp[i-j])，取两个数乘积或多个数乘积的最大值
初始化 dp[2]=1
遍历顺序 i从3开始，j从i开始

代码

class Solution:
    # dp[i]表示将i进行分解得到的最大乘积
    # 递归公式 dp[i] = max(j*(i-j), j*dp[i-j])，取两个数乘积或多个数乘积的最大值
    # 初始化 dp[2]=1
    # 遍历顺序 i从3开始，j从i开始
    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 - 1):
                dp[i] = max(dp[i], j * (i - j), j * dp[i - j])
        return dp[n]
1
2
3
4
5
6
7
8
9
10
11
12

96.不同的二叉搜索树

思路分析

需要从头分析，看树的形状，找规律
dp[i] 由i个节点构成二叉搜索树的种数
dp[i] = dp[0] * dp[i-1] + dp[1] * dp[i-2] + … + dp[i-1]*dp[0]
dp[左子树节点个数]*dp[右子树节点个数]
代码随想录思路

代码

class Solution:
    # 需要从头分析，看树的形状，找规律
    # dp[i] 由i个节点构成二叉搜索树的种数
    # dp[i] = dp[0] * dp[i-1] + dp[1] * dp[i-2] + ... + dp[i-1]*dp[0]
    # dp[左子树节点个数]*dp[右子树节点个数]
    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]
1
2
3
4
5
6
7
8
9
10
11
12