最短路径问题

第一题：求不重复路径的个数

How many possible unique paths are there A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

• 问题:

问的是有多少种路径（而不是多少步）

从path(1,1) 到path(1,4) 只能一直超右走 属于一种路径

• 推理

都依赖path（1，1）这个节点 必须初始化

• 递归实现

Status:

Time Limit Exceeded 时间限制条件：

• 分析

访问节点 paths(2,1) 时候计需要计算1次 在次访问访问节点 paths(2,1) 时候计需要计算1次 每个节点被访问2次 ，需要计算2次 Note:m and n will be at most 100. m=23 n=12 时候 path=193536720 有一亿个路径 性能o(n 次方m)

• 需要空间记录以前计算结果

class Solution {
public:
int uniquePaths(int m, int n) {
if(m ==0 ||n ==0)
{
return 0;
}
if(m ==1 && n==1)
{
return 1;
}
if(result[m][n]>0) return result[m][n];//paths(m,n)计算过了
int left=uniquePaths(m-1,n);
int right=uniquePaths(m,n-1);
result[m][n]=left+right;
return result[m][n];
}
public:
map<int, map<int, int>> result;
}

• 动态规划实现

第二题：求不重复路径的个数Unique Paths

Now consider if some obstacles are added to the grids. How many unique paths would there be? An obstacle and empty space is marked as 1 and 0 respectively in the grid. 在网格中，障碍物和空白分别被标记为1和0，有障碍物表示路径不能通过

• 审题：

• 分析

-

• 测试：

input：[[1]] output：0

input：[[0]] output：1

• 代码

int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int m = obstacleGrid.size();
int n = obstacleGrid[0].size();
vector<vector<int>> dp(m+1,vector<int>(n+1,0));
if(obstacleGrid[0][0]==1)
{
dp[1][1]=0;
}else
{
dp[1][1]=1;
}
for(int i = 1 ; i <= m ; ++i)
for(int j = 1 ; j <= n ; ++j)
{
if(i ==1 &&j ==1)
{
continue;
}else if(!obstacleGrid[i-1][j-1]) //dp 比ob多一行列
{
dp[i][j] = dp[i-1][j]+dp[i][j-1];
}
}
return dp[m][n];
}
};

第三题：最短路径

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path. Note: You can only move either down or right at any point in time.

• 分类：最短路径
• 审题：

从dp[0][0] 到dp[m-1][n-1] 存在这无数路径，求最小路径（sum of all numbers）

• 公式

dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j] i>=1 j>=1 但i=0 ||j=0的时候不满足条件 边界问题

• code

int minPathSum(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
vector<vector<int>> dp(m,vector<int>(n,0));
dp[0][0]=grid[0][0];
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
//初始化
if(i ==0 &&j==0)
{
continue;
}else if(i ==0)
{
dp[i][j]=dp[i][j-1]+grid[i][j];
} else if(j==0)
{
dp[i][j]=dp[i-1][j]+grid[i][j];
}else
{ //状态转移方式
dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j];
}
}
}
return dp[m-1][n-1];
}

• 测试case： input: [1,3,1] m=1 n=3 从dp[0][0]到dp[0][2] 只有一个路径

总结：

递归：从下朝上推到 依赖下个元素 必须初始化最后一个元素 动态规划：从上到下推倒 依赖上个元素结果 必须初始化第一个元素