【刷题笔记】——day.4 路径问题总结

学习目标：

用于记录每日刷的题目为了明年的python组蓝桥杯做准备，今天是打卡的第四天，冲！

原题一 ：不同路径

题目描述：

一个机器人位于一个 m x n 网格的左上角 。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角，问总共有多少条不同的路径？

示例一： 

输入：m = 3, n = 7
输出：28

示例二： 

输入：m = 3, n = 2
输出：3

 题解：

思路(动态规划)：

1.由于机器人只能向下或向右走，所以对于每个点的路径就等于每个点上位置和左位置的路径的总和。

2.机器人从(0,0)出发，到达(m-1,n-1)终点，要用动态规划，首先要明确dp[i][j]的含义和其下标的含义,dp[i][j]:表示从(0,0)出发到达(i,j)的总路径数。

3.确定递推公式，自然的就能写出 dp[i][j] = dp[i-1][j] + dp[i][j-1]

4.特殊位置: 对于第一行格子，只能从左边到达 所以递推公式为 dp[i][j] = dp[i][j-1] ;

同理对于第一列的格子，只能从上边到达 所以递推公式为 dp[i][j] = dp[i-1][j]

 代码实现(python):

def uniquePaths(m, n):
    dp = [[0]*n]*m   #定义一个m*n维的矩阵
    for i in range(m):
        for j in range(n):
            if i == 0 and j == 0:   #初始化 dp[0][0]
                dp[i][j] = 1
                continue
            if i > 0 and j > 0:
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
            elif i > 0:
                dp[i][j] = dp[i-1][j]
            elif j > 0:
                dp[i][j] = dp[i][j-1]
    return dp[m-1][n-1]

原题二：不同路径II

题目描述:

一个机器人位于一个 m x n 网格的左上角 ,机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角,现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？网格中的障碍物和空位置分别用 1 和 0 来表示。

示例一 ：

输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2

示例二: 

输入：obstacleGrid = [[0,1],[0,0]]
输出：1 

  题解：

 思路(动态规划)：

与上题的思路类似，只是在基础上加上了障碍物。不难想到，只要判断 obstacleGrid[i][j]是否初始值是 1。如果是 1，则没有路能到达，对应的 dp[i][j] =0，其他的思想和上题类似。

代码实现(Python):

class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid):
        row = len(obstacleGrid)   
        column = len(obstacleGrid[0])
        if obstacleGrid[0][0]==1:   #如果[0][0]点有障碍物，则无法到达终点
            return 0
        obstacleGrid[0][0]=1   #初始化dp[0][0]
        for i in range(row):
            for j in range(column):
                if i==0 and j==0:
                    continue
                if obstacleGrid[i][j] == 1:  #如果有障碍物，则让dp[i][j] = 0
                    obstacleGrid[i][j] = 0
                    continue
                if i>0 and j>0:
                    obstacleGrid[i][j] = obstacleGrid[i-1][j]+obstacleGrid[i][j-1]
                elif i>0:
                    obstacleGrid[i][j] = obstacleGrid[i-1][j]
                elif j>0:
                    obstacleGrid[i][j] = obstacleGrid[i][j-1]
        return obstacleGrid[row-1][column-1]

 原题三：最小路径和

题目描述：

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：每次只能向下或者向右移动一步。

示例一： 

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1 到 3 到 1 到 1 到 1 的总和最小。

示例二：

输入：grid = [[1,2,3],[4,5,6]]
输出：12

题解：

思路(动态规划)：

1.与前两道题类似，只是再原先的基础将路线上加权，求经过的路线权和的最小值。0

2.结合上两道题的思路，递推则为每个点的权数加上左边路径的最小权和或上边路径的最小权和的最小值，很容易就能写出新的递推公式 dp[i][j] = grid[i][j] + min(dp[i-1][j],dp[i][j-1])。

 代码实现(Python)：

class Solution:
    def minPathSum(self, grid):
        row = len(grid)  #确定行数
        column = len(grid[0])   #确定列数
        dp = [[0]*column]*row
        for i in range(row):
            for j in range(column):
                if i == 0 and j==0:
                    dp[0][0] = grid[0][0]
                if i > 0 and j >0:
                    dp[i][j] = grid[i][j]+min(dp[i-1][j],dp[i][j-1])  #递推
                elif i > 0:
                    dp[i][j] = grid[i][j] + dp[i-1][j]   #边界情况
                elif j >0:
                    dp[i][j] = grid[i][j] + dp[i][j-1]   #边界情况
        return dp[row-1][column-1]