专栏：50多种数据结构彻底征服
专栏：50多种经典图论算法全部掌握
最近一网友发文说入职华为四个月，天天十一点半到家，加班太累想跑路了。之前也发过一篇文章关于加班的问题，有些人说只要钱给的够，9117都没问题，实际上体力劳动和脑力劳动还是有差别的，如果真的让你9117估计也是扛不住的。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是LeetCode的第62题：不同路径。
问题描述
来源：LeetCode第62题
难度：中等
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。问总共有多少条不同的路径？
示例1：
输入：m = 3, n = 7 输出：28
示例2：
输入：m = 7, n = 3 输出：28
1 <= m, n <= 100
题目数据保证答案小于等于 2 * 10^9
问题分析
这题是让计算从左上角到右下角总共有多少种不同的路径，并且 每次只能往下或者往右走 。
我们使用动态规划来解决这道题，定义 dp[i][j] 表示从左上角到坐标 [i,j] 总共有多少种不同的路径 。
要走到坐标 [i,j] 只能有两个方向，一个是从上面走下来，一个是从左边走过来，所以总的路径个数就是它俩之和，也就是：
dp[i][j]=dp[i-1][j]+dp[i][j-1]
这里要注意第一行上面是没有元素的，第一列左边也是没有的，所以第一行和第一列要单独处理。当然这里也可以优化，就是把二维数组变成一维数组来解。
JAVA：
public int uniquePaths(int m, int n) { int[][] dp = new int[m][n]; for (int i = 0; i < n; i++) // 第一行都是1 dp[0][i] = 1; for (int i = 0; i < m; i++)// 第一列都是1 dp[i][0] = 1; // 这里是递推公式 for (int i = 1; i < m; i++) for (int j = 1; j < n; j++) dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; return dp[m - 1][n - 1]; }C++：
public: int uniquePaths(int m, int n) { vector
> dp(m, vector
(n, 0)); for (int i = 0; i < n; i++) // 第一行都是1 dp[0][i] = 1; for (int i = 0; i < m; i++)// 第一列都是1 dp[i][0] = 1; // 这里是递推公式 for (int i = 1; i < m; i++) for (int j = 1; j < n; j++) dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; return dp[m - 1][n - 1]; }
Python：
def uniquePaths(self, m: int, n: int) -> int: dp = [[0 for _ in range(n)] for _ in range(m)] for i in range(n): # 第一行都是1 dp[0][i] = 1 for i in range(m): # 第一列都是1 dp[i][0] = 1 # 这里是递推公式 for i in range(1, m): for j in range(1, n): dp[i][j] = dp[i - 1][j] + dp[i][j - 1] return dp[m - 1][n - 1]笔者简介
博哥，真名：王一博，毕业十多年， 作者，专注于 数据结构和算法 的讲解，在全球30多个算法网站中累计做题2000多道，在公众号中写算法题解800多题，对算法题有自己独特的解题思路和解题技巧，喜欢的可以给个关注，也可以 下载我整理的1000多页的PDF算法文档 。
热门跟贴