專欄：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算法文檔 。