[代码随想录]Day35-动态规划part03

WtcSky / 2023-09-04 / 原文

题目：343. 整数拆分

思路：

状态转移方程：dp[i] = max(dp[i], max((i-j)*j,dp[i-j]*j))，其中(i-j)*j是把i分成了两个数，dp[i-j]*j是把(i-j)分成了两个数及以上(也就是说这个式子代表3个数及以上)。因为dp是状态转移，是前面数的最优解，所以不需要考虑到底分成了几个数。
其实只有前面几个是走了(i-j)*j，后面的式子全部都是走的dp[i-j]*j

代码：

func integerBreak(n int) int {
    dp := make([]int, n+1)
    dp[2] = 1 // 2只能分成1、1结果是 1 * 1 = 1
    for i:=3; i<=n;i++ {
        for j:=1; j<=i/2; j++ { // 当然可以直接<=i-1，这样写可以优化一点(靠近中间更大)
            dp[i] = max(dp[i], max((i-j)*j,dp[i-j]*j))
        }
    }
    return dp[n]
}

func max(a,b int) int {
    if a > b {
        return a 
    }
    return b
}

参考：

代码随想录

题目：96. 不同的二叉搜索树

思路：

重点不是节点数，而是节点的布局，这道题就算没有数也无所谓，直接问最多有多少种布局：
以3(i)个节点为例：

左0右2 (0 i-1)
左1右1 (1 i-2)
左2右0 (2 i-3)

即dp[3] = dp[0]*dp[2] + dp[1]*dp[1] + dp[2]*dp[0]

代码：

func numTrees(n int) int {
    dp := make([]int, n+1)
    dp[0] = 1
    for i := 1; i <= n; i++ {
        for j := 0; j < i; j++ {
            dp[i] += dp[i-j-1] * dp[j]
        }
    }
    return dp[n]
}