代码随想录算法训练营第二十九天｜LeetCode 62. 不同路径、 63. 不同路径 II、 343. 整数拆分

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

题目链接：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]格时向下走一格。

动态规划五部曲：

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

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。

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

如果开头或结尾为障碍物，则从开始走到结果的可能性为0
如果第一行/第一列有障碍物，则从第一行的障碍物往右/第一列障碍物往下都是走不到的地方了，因此这些走不到的地方的初始化为0，走得到的初始化还是为1
遍历中遇到中间的障碍物了，直接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并不难！