今天是动态规划的第二天！今天稍微加点难度，不仅有涉及二维数组，还有涉及 有难度的思考递推公式的题！

题目链接：62. 不同路径

状态：思路不难，套用模版，直接AC。

在上一篇中，爬楼梯题目中，我学会了当一次可以爬1阶或2阶楼梯时，那么 到达第n层楼梯的方法数 = 到达第n-1层楼梯的方法数 + 到达第n-2层楼梯的方法数。这是因为 可以看成从第n-1阶爬1阶到达 或 从n-2阶爬2阶到达。
相同的道理，到达第[i][j]格时的方法总数 = 到达第[i-1][j]格时的方法总数 + 到达第[i][j-1]格时的方法总数。因为可以看成是 到达第[i-1][j]格时 向右走一格 或 到达第[i][j-1]格时 向下走一格。

动态规划五部曲：

1. dp[i][j] 表示 到达[i][j]格时的方法总数
2. 递推公式 上述提过。因此dp[i][j] = dp[i-1][j] + dp[i][j-1]
3. 初始化。第一行和第一列都要为1。因为只有 横着一直向右/竖着一直向下 这一种方法可以到达第一行/第一列的格子
4. 遍历。从左向右，从上到下的遍历。这是因为题目的基调就是机器人从左上往右下走，且机器人只能右移或下移
5. 想测试的话可以打印。
   综上所述，完整代码如下:

class Solution: // Python
    def uniquePaths(self, m: int, n: int) -> int:
        # Create a two-dimensional list to store the number of unique paths
        dp = [[0] * n for _ in range(m)]
        
        #initialization
        for i in range(m):
            dp[i][0] = 1
        for j in range(n):
            dp[0][j] = 1
        
        # Count the number of unique paths to each cell
        for i in range(1,m):
            for j in range(1,n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        
        # Returns the number of unique paths to the bottom right cell
        return dp[m-1][n-1]

复杂度分析：
时间复杂度：O(mn). 初始化是O(m)+O(n)， 但是两层for循环遍历每个格子的时候是O(mn)
空间复杂度：O(mn). 用了一个mn的二维列表

题目链接：63. 不同路径 II

状态：核心思路不变，套用模版，直接AC。

本题核心思路不变，只是需要处理一下遇到障碍物的情况。

1. 如果开头或结尾为障碍物，则从开始走到结果的可能性为0
2. 如果第一行/第一列有障碍物，则从 第一行的障碍物往右/第一列障碍物往下 都是走不到的地方了，因此这些走不到的地方的初始化为0，走得到的 初始化还是为1
3. 遍历中遇到中间的障碍物了，直接continue到下一次循环就好

动态规划五部曲同上。三种遇到障碍物的情况分别对应了开头的判断、初始化的处理、以及循环时的处理。
综上所述，完整代码如下:

class Solution: // Python
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        m = len(obstacleGrid) # Number of grid rows
        n = len(obstacleGrid[0]) # Number of columns in the grid

        # If there is an obstacle at the start or end point, return 0 directly
        if obstacleGrid[0][0] == 1 or obstacleGrid[m-1][n-1] == 1:
            return 0

        # Create a two-dimensional list to store the path number
        dp = [[0] * n for _ in range(m)]

        # initialization
        # When encountering an obstacle, exit the loop directly, and the default value is 0.
        for i in range(m):
            if obstacleGrid[i][0] == 0:
                dp[i][0] = 1
            else:
                break
        
        for j in range(n):
            if obstacleGrid[0][j] == 0:
                dp[0][j] = 1
            else:
                break
        
        # Core logic: Calculate the number of paths to other locations
        for i in range(1,m):
            for j in range(1,n):
                if obstacleGrid[i][j] == 1:
                    continue
                dp[i][j] = dp[i-1][j] + dp[i][j-1]

        return dp[m-1][n-1]

复杂度分析同上。

题目链接：343. 整数拆分

状态：分析好五部曲之后，一次性AC并不难！

动态规划五部曲：

1. dp[i]。 数字为i时，dp[i]表示拆分数字i所获的最大乘积。
2. 递推公式。在拆分过程中，有两种情况：一、把i拆分成j与i-j两个数。二、把i-j继续拆分。因此两种情况的乘积结果分别表示为 j * (i-j)、j * dp[i-j]。因此，在遍历过程中取最大值就好，但是别忘了取最大值的时候还要带上dp[i]本身。
3. 初始化。dp[0]和dp[1]根本没意义，所以不管。dp[2]只有一种拆法且结果为1所以就把dp[2]初始化为1就好了。
4. 遍历。从小到大遍历，因为后面的值依赖前面的结果。
5. 想测试的话可以打印。
   综上所述，完整代码如下：

class Solution: // Python
    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, n // 2 + 1):
                dp[i] = max(dp[i], j * (i - j), j * dp[i-j])
        
        return dp[n]

复杂度分析：
时间复杂度：O(n ^ 2). 两层for循环就是n^2了
空间复杂度：O(n). 大小为n+1的数组