最短路径问题

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

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] 只有一个路径

总结:

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

原文发布于微信公众号 - 架构说(JiaGouS)

原文发表时间:2018-03-18

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Ryan Miao

附近的人位置距离计算方法

附近的人的位置用经纬度表示,然后通过两点的经纬度计算距离。根据网上的推荐,最终采用geohash。 geohash的实现java版: 1 import ja...

65670
来自专栏竹清助手

深入理解 Laravel Eloquent(三)——模型间关系(关联)

Eloquent 是一个 ORM,全称为 Object Relational Mapping,翻译为 “对象关系映射”(如果只把它当成 Database A...

14330
来自专栏Crossin的编程教室

【每周一坑】生成词云

来看本周的题目。 使用 wordcloud 生成词云图 ? 在 Python 中有许多有趣的库可供学习, wordcloud 必须得算一个,本周我们的题目就是,...

389110
来自专栏冰霜之地

Google S2 中的四叉树求 LCA 最近公共祖先

首先需要回顾一下希尔伯特曲线的生成方式,具体代码见笔者上篇文章的分析,在这个分析中,有4个方向比较重要,接下来的分析需要,所以把这4个方向的图搬过来。

13230
来自专栏java一日一条

Python算法:如何解决回文索引问题

对于这个问题野蛮的解决方案是遍历S中每个单词大小的窗口并检查它们是否是回文,如下所示:

10320
来自专栏Golang语言社区

Go项目开发----2048小游戏(下)

//向左旋转90度 func (t *G2048)left90() { tn := new(G2048) for i, line := range t...

47370
来自专栏java技术学习之道

海量数据处理 - 找出最大的n个数(top K问题)

70040
来自专栏生信技能树

可能只是一个函数,却要耗费你大半天

好像不少人问过我一个聚类后的树如何根据肉眼观察到的cluster情况来提前指定的树的子集,有点类似于WGCNA分析把几千个基因划分成若干个module后能提取各...

14630
来自专栏用户画像

3.2 组帧

数据链路层之所以要把比特组合成帧为单位传输,是为了在出错时只重发出错的帧,而不必重发全部数据,从而提高了效率。为了使接收方能正确地接受并检查所传输的帧,发送方必...

8710
来自专栏Python绿色通道

数据分析 | Numpy初窥1

由于Numpy提供了一个简单易用的C API,因此很容易将数据传输给由低级语言编写的外部库,外部库也能以Numpy数组的形式将数据返回给Python

15320

扫码关注云+社区

领取腾讯云代金券