本文共 5589 字，大约阅读时间需要 18 分钟。

原题目

第一题

问总共有多少条不同的路径？

例如，上图是一个7 x 3 的网格。有多少可能的路径？

说明：m 和 n 的值均不超过 100。

示例 1:

输入: m = 3, n = 2

输出: 3

解释:

从左上角开始，总共有 3 条路径可以到达右下角。

\1. 向右 -> 向右 -> 向下

\2. 向右 -> 向下 -> 向右

\3. 向下 -> 向右 -> 向右

示例 2:

输入: m = 7, n = 3

输出: 28

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/unique-paths

第二题

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中记为“Finish”）。

现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？

网格中的障碍物和空位置分别用 1 和 0 来表示。

说明：m 和 n 的值均不超过 100。

示例 1:

输入:

[

[0,0,0],

[0,1,0],

[0,0,0]

]

输出: 2

解释:

3x3 网格的正中间有一个障碍物。

从左上角到右下角一共有 2 条不同的路径：

\1. 向右 -> 向右 -> 向下 -> 向下

\2. 向下 -> 向下 -> 向右 -> 向右

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/unique-paths-ii

第三题

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

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

示例:

输入:

[

[1,3,1],

[1,5,1],

[4,2,1]

]

输出: 7

解释: 因为路径 1→3→1→1→1 的总和最小。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/minimum-path-sum

题目分析

第一题

方法零：公式法

我们用 R 表示向右，D 表示向下，然后把所有路线写出来，就会发现神奇的事情了。 R R R D D R R D D R R D R D R ……

从左上角，到右下角，总会是 3 个 R，2 个 D，只是出现的顺序不一样。所以求解法，本质上是求了组合数，N = m + n - 2，也就是总共走的步数。 k = m - 1，也就是向下的步数，D 的个数。所以总共的解就是 Cn-k=n!/(k!(n-k)!)=(n*(n-1)(n-2)(n-k+1)/k!。

方法一：深搜 超时 方法二：记忆化搜索 方法三：二维动态规划 动态转移方程dp[i][j]=dp[i][j-1]+dp[i-1][j]

1	1	1	1	1	1	1
1	2	3	4	5	6	7
1	3	6	10	15	21	28

方法四：一维动态规划dp[i]=dp[i-1]+dp[i]

第二题

在第一题的基础上判断当前位置是否有障碍物，有则置为0

方法一：深搜 超时 方法二：记忆化搜索 方法三：二维动态规划 动态转移方程 dp[i][j]=dp[i][j-1]+dp[i-1][j] if(obs[i]==1)dp[i][j]=0; 例子： 输入: [ [0,0,0], [0,1,0], [0,0,0] ] 输出: 2

1	1	1
1	0	1
1	1	2

方法四：一维动态规划

dp[i]=dp[i-1]+dp[i] if(obs[i]==1)dp[i][j]=0; 方法五：原数组存储动态规划

第三题

方法一：深搜 超时

方法二：记忆化搜索 方法三：二维动态规划 方法四：一维动态规划 方法五：原数组存储动态规划

完整代码

方法零

int uniquePaths(int m, int n){       int N=m+n-2;    int k=m-1;    long res=1;    for(int i=1;i<=k;i++)        res=res*(N-k+i)/i;    return (int)res;}

方法一

int uniquePaths(int m, int n){       if(m==1&&n==1)    {           return 1;    }    int res=0;    if(m>1)        res+=uniquePaths(m-1,n);    if(n>1)        res+=uniquePaths(m,n-1);    return res;}

方法二：

int vis[101][101];int dfs(int m,int n){       if(m==0&&n==0)    {           return 1;    }    if(vis[m][n])    {          return vis[m][n];     }    int res=0;    if(m>0)        res+=dfs(m-1,n);    if(n>0)        res+=dfs(m,n-1);    vis[m][n]=res;        return res;}int uniquePaths(int m, int n){       memset(vis,0,sizeof(vis));    return dfs(m-1,n-1);}

方法三

int dp[101][101];int uniquePaths(int m, int n){       for(int k=0; k

方法四

int uniquePaths(int m, int n){       if(m==0||n==0)return 0;    int *dp=(int *)malloc(sizeof(int)*n);    dp[0]=0;    for(int i=0;i

第二题

方法一：

int dfs(int **obs,int m,int n){       if(obs[m][n]==1)return 0;    if(m==0&&n==0)      return 1;    int res=0;    if(m>0)        res+=dfs(obs,m-1,n);    if(n>0)        res+=dfs(obs,m,n-1);    return res;}int uniquePathsWithObstacles(int** obstacleGrid, int obstacleGridSize, int* obstacleGridColSize){       return dfs(obstacleGrid,obstacleGridSize-1,obstacleGridColSize[0]-1);}

方法二：

int vis[100][100];int dfs(int **obs,int m,int n){       if(obs[m][n]==1)return 0;    if(m==0&&n==0)return 1;    if(vis[m][n])return vis[m][n];    int res=0;    if(m>0)        res+=dfs(obs,m-1,n);    if(n>0)        res+=dfs(obs,m,n-1);   vis[m][n]=res;     return res;}int uniquePathsWithObstacles(int** obstacleGrid, int obstacleGridSize, int* obstacleGridColSize){       memset(vis,0,sizeof(vis));    return dfs(obstacleGrid,obstacleGridSize-1,obstacleGridColSize[0]-1);}int vis[100][100];int dfs(int **obs,int m,int n){       if(obs[m][n]==1)return 0;    if(m==0&&n==0)return 1;    if(vis[m][n])return vis[m][n];    int res=0;    if(m>0)        res+=dfs(obs,m-1,n);    if(n>0)        res+=dfs(obs,m,n-1);   vis[m][n]=res;     return res;}int uniquePathsWithObstacles(int** obstacleGrid, int obstacleGridSize, int* obstacleGridColSize){       memset(vis,0,sizeof(vis));    return dfs(obstacleGrid,obstacleGridSize-1,obstacleGridColSize[0]-1);}

方法三：

略 方法四：

int uniquePathsWithObstacles(int** obstacleGrid, int obstacleGridSize, int* obstacleGridColSize){       int m=obstacleGridSize;    int n=obstacleGridColSize[0];//printf("%d %d\n",n,m);    long *dp=(long*)malloc(sizeof(long)*n);    memset(dp,0,n*sizeof(long));    dp[0]=1;    for(int i=0;i
   
    0)                dp[j]+=dp[j-1];                    }    return (int)dp[n-1];}
   

方法五

int uniquePathsWithObstacles(int** obstacleGrid, int obstacleGridSize, int* obstacleGridColSize){       for(int i = 0; i

第三题

方法一：

int dfs(int **grid,int m,int n){       if(m<0||n<0)return INT_MAX;    if(m==0&&n==0)      return grid[m][n];    return fmin(dfs(grid,m-1,n),dfs(grid,m,n-1))+grid[m][n];}int minPathSum(int** grid, int gridSize, int* gridColSize){       if(gridSize==0||gridColSize[0]==0)return 0;    return dfs(grid,gridSize-1,gridColSize[0]-1);}

方法二：

int vis[500][500];int dfs(int **grid,int m,int n){       if(m<0||n<0)return INT_MAX;    if(m==0&&n==0)      return grid[m][n];    if(vis[m][n])return vis[m][n];    vis[m][n]=grid[m][n]+fmin(dfs(grid,m-1,n),dfs(grid,m,n-1));    return vis[m][n];}int minPathSum(int** grid, int gridSize, int* gridColSize){       if(gridSize==0||gridColSize[0]==0)return 0;    memset(vis,0,sizeof(vis));    return dfs(grid,gridSize-1,gridColSize[0]-1);}

方法三

int minPathSum(int** grid, int gridSize, int* gridColSize){       int **dp=(int **)malloc(sizeof(int *)*gridSize);    for(int i=0;i

方法四：

int minPathSum(int** grid, int gridSize, int* gridColSize){       int m=gridSize;    int n=gridColSize[0];    int *dp=(int *)malloc(sizeof(int)*n);    for(int i=0;i

方法五：

int minPathSum(int** grid, int gridSize, int* gridColSize){       int m=gridSize;    int n=gridColSize[0];    for(int i=0;i

转载地址：http://juhtz.baihongyu.com/