从一个年薪60+万要不要到小红书的年薪百万，看到这个我都想去了，果然还是算法工程师工资高，搞算法还是很有前途的，所以大家没事都可以过来学两道算法题，长此以往还是很有好处的。
有网友评论说：趁着年轻多挣钱，反正从毕业到失业就十年的时间，哪给的多就去哪。
--------------下面是今天的算法题--------------
来看下今天的算法题，这题是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算法文档 。