代码随想录算法营Day38 ｜ 62. 不同路径，63. 不同路径 II，343. 整数拆分，96. 不同的二叉搜索树

62. 不同路径

这题的限制是机器人在m x n的网格的左上角，每次只能向下走一格或者向右走一格。问到右下角有多少条不同路径。这个动态规划的初始状态是第一行和第一列的格子的值都是1，因为机器人只能向右走一格或者向下走一格，所以第一行和第一列的格子的不同路径数只能是1.而其他格子的路径数取决于每个格子的正上方和左边两个格子的路径数之和，即状态转移公式为

 dp[i][j] = dp[i-1][j] + dp[i][j-1]。

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[0] * n for _ in range(m)]
        for i in range(m):
            dp[i][0] = 1
        for i in range(n):
            dp[0][i] = 1
        for x in range(1,m):
            for y in range(1,n):
                dp[x][y] = dp[x-1][y] + dp[x][y-1]
        return dp[m-1][n-1]

63. 不同路径 II

这道题比上道题多了一个条件就是网格图中多了障碍物。但并不影响整体的思路，不过就是在状态初始化的时候遇到障碍物后就终止循环。在进行状态转移的时候也只更新非障碍物格子的值即可。

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m,n = len(obstacleGrid),len(obstacleGrid[0])
        dp = [[0] * n for _ in range(m)]
        for i in range(m):
            if obstacleGrid[i][0] == 1:
                break
            else:
                dp[i][0] = 1
        for i in range(n):
            if obstacleGrid[0][i] == 1:
                break
            else:
                dp[0][i] = 1
        for i in range(1,m):
            for j in range(1,n):
                if obstacleGrid[i][j] == 0:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
        return dp[m-1][n-1]

343. 整数拆分

这题我们从小到大一点点拆，每次dp记录该数所拆出来的正整数的最大乘积。所以状态转移公式就是

dp[i] = max(dp[i],max([(i-j)*j,dp[i-j]*j))

这里的i代表要拆的数字，j代表拆出去的某个正整数，这里面又比较了一次(i-j)*j和dp[i-j]*j是因为这个数所拆出来的正整数的最大乘积未必有他自身大，所以我们需要判断是直接取这个数本身还是dp记录的该数所拆出来的正整数的最大乘积。

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

96. 不同的二叉搜索树

这题分析，当n为1的时候，只有1种，当n为2的时候，有2种，当n为3的时候，总共可以有5种。那么我们就可以发现当dp[3]的时候就是 元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量那么状态转移公式就是：

dp[i] += dp[j-1] * dp[i-j]

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]