摘要:作者碼蹄疾畢業于哈爾濱工業大學。機器人試圖達到網格的右下角在下圖中標記為。問總共有多少條不同的路徑例如,上圖是一個的網格。有多少可能的路徑說明和的值均不超過。示例輸入輸出解釋從左上角開始,總共有條路徑可以到達右下角。
作者: 碼蹄疾題目
畢業于哈爾濱工業大學。 小米廣告第三代廣告引擎的設計者、開發者;
負責小米應用商店、日歷、開屏廣告業務線研發;
主導小米廣告引擎多個模塊重構;
關注推薦、搜索、廣告領域相關知識;
一個機器人位于一個 m x n 網格的左上角 (起始點在下圖中標記為“Start” )。
機器人每次只能向下或者向右移動一步。機器人試圖達到網格的右下角(在下圖中標記為“Finish”)。
問總共有多少條不同的路徑?
例如,上圖是一個7 x 3 的網格。有多少可能的路徑?
說明:m 和 n 的值均不超過 100。
示例 1:
輸入: m = 3, n = 2 輸出: 3 解釋: 從左上角開始,總共有 3 條路徑可以到達右下角。 1. 向右 -> 向右 -> 向下 2. 向右 -> 向下 -> 向右 3. 向下 -> 向右 -> 向右
示例 2:
輸入: m = 7, n = 3 輸出: 28題解
這道題拿到題目我覺得大家的第一反應都是這應該是遞歸的題目,因為我們可以轉化為子問題,但是這樣暴力肯定會超時,就不用嘗試了。其實在該題遞歸的方法就是從上面到下面不斷的去嘗試,如果我們能記住之前的結果,就對我們下一步有幫助,所以想到了DP的方法。
格子中的數字代表當前的方法.
初始狀態
當前這個狀態只和左邊和上邊的格子有關系.
依次求解
于是我們可以得到狀態轉移方程:
ways[i][j] = ways[i-1][j] + ways[i][j-1];java代碼
public class Solution { public int uniquePaths(int m, int n) { int[][] ways = new int[m][n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (i == 0 || j == 0) ways[i][j] = 1; else ways[i][j] = ways[i-1][j] + ways[i][j-1]; } } return ways[m-1][n-1]; } }優化
上面圖3我們在求解的時候,我們是一行一行求解的,實際上我們只需要記錄遍歷到(i, j)這個位置的時候當前行有幾種路徑,如果遍歷到(i, m-1)的時候,替換掉這一行對應列的路徑即可,于是狀態轉移方程編程:
res[j] = res[j] + res[j-1]
class Solution { public int uniquePaths(int m, int n) { if (m <= 0 || n <= 0) { return 0; } int[] res = new int[n]; res[0] = 1; for (int i = 0; i < m; i++) { for (int j = 1; j < n; j++) { res[j] += res[j - 1]; System.out.println("i=" + i + "_" + "j=" + j + ":" + Arrays.toString(res)); } } return res[n - 1]; } }
有的同學可能還是不理解,我在代碼里面打印了一些信息方便理解:
i=0_j=1:[1, 1, 0, 0, 0, 0, 0] i=0_j=2:[1, 1, 1, 0, 0, 0, 0] i=0_j=3:[1, 1, 1, 1, 0, 0, 0] i=0_j=4:[1, 1, 1, 1, 1, 0, 0] i=0_j=5:[1, 1, 1, 1, 1, 1, 0] i=0_j=6:[1, 1, 1, 1, 1, 1, 1] //只記錄到這一行的信息 i=1_j=1:[1, 2, 1, 1, 1, 1, 1] i=1_j=2:[1, 2, 3, 1, 1, 1, 1] i=1_j=3:[1, 2, 3, 4, 1, 1, 1] i=1_j=4:[1, 2, 3, 4, 5, 1, 1] i=1_j=5:[1, 2, 3, 4, 5, 6, 1] i=1_j=6:[1, 2, 3, 4, 5, 6, 7] //只記錄到這一行的信息 i=2_j=1:[1, 3, 3, 4, 5, 6, 7] i=2_j=2:[1, 3, 6, 4, 5, 6, 7] i=2_j=3:[1, 3, 6, 10, 5, 6, 7] i=2_j=4:[1, 3, 6, 10, 15, 6, 7] i=2_j=5:[1, 3, 6, 10, 15, 21, 7] i=2_j=6:[1, 3, 6, 10, 15, 21, 28] //只記錄到這一行的信息 i=3_j=1:[1, 4, 6, 10, 15, 21, 28] i=3_j=2:[1, 4, 10, 10, 15, 21, 28] i=3_j=3:[1, 4, 10, 20, 15, 21, 28] i=3_j=4:[1, 4, 10, 20, 35, 21, 28] i=3_j=5:[1, 4, 10, 20, 35, 56, 28] i=3_j=6:[1, 4, 10, 20, 35, 56, 84] //只記錄到這一行的信息Math
這個題其實可以用排列組合的方式來做。這其實是最開始想到的方法。
以模擬的[4, 7]的例子,每一條路徑:
向右的肯定有6步;
向左的肯定有3步;
問題即為:c(9,3) = (9 8 7) / (1 2 3) = 84
組合數公式:c(m,n) = m! / (n! * (m - n)!)
java代碼java直接套用公式會越界,下面結果我用long存儲:
1!=1 2!=2 3!=6 4!=24 5!=120 6!=720 7!=5040 8!=40320 9!=362880 10!=3628800 11!=39916800 12!=479001600 13!=6227020800 14!=87178291200 15!=1307674368000 16!=20922789888000 17!=355687428096000 18!=6402373705728000 19!=121645100408832000 20!=2432902008176640000 21!=-4249290049419214848 22!=-1250660718674968576 23!=8128291617894825984 24!=-7835185981329244160
需要稍微化簡一下,化簡的過程就是我求解c(9,3)的第二步驟。
class Solution { public int uniquePaths(int m, int n) { double dom = 1; double dedom = 1; int small = m < n ? m - 1 : n - 1; int big = m < n ? n - 1 : m - 1; for (int i = 1; i <= small; i++) { dedom *= i; dom *= small + big + 1 - i; } return (int) (dom / dedom); } }python代碼
python代碼就比較兇殘了,一行代碼搞定:
class Solution: def uniquePaths(self, m, n): return int(math.factorial(m + n - 2) / math.factorial(m -1) / math.factorial(n-1))
貼一下DP版本的代碼
class Solution: def uniquePaths(self, m, n): """ :type m: int :type n: int :rtype: int """ if m <= 0 or n <= 0: return 0 res = [0 for _ in range(0, n)] res[0] = 1 for i in range(0, m): for j in range(1, n): res[j] += res[j-1] return res[n-1]熱門閱讀
【Leetcode】61.旋轉鏈表
【Leetcode】60. 第k個排列
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/42404.html
摘要:作者碼蹄疾畢業于哈爾濱工業大學。機器人試圖達到網格的右下角在下圖中標記為。問總共有多少條不同的路徑例如,上圖是一個的網格。有多少可能的路徑說明和的值均不超過。示例輸入輸出解釋從左上角開始,總共有條路徑可以到達右下角。 作者: 碼蹄疾畢業于哈爾濱工業大學。 小米廣告第三代廣告引擎的設計者、開發者;負責小米應用商店、日歷、開屏廣告業務線研發;主導小米廣告引擎多個模塊重構;關注推薦、搜索、廣...
摘要:問一共有多少條獨特的路線思路一通過遞歸實現計算。思路二楊輝三角在思路的指引下,我們可以嘗試將遞歸的方法改變為循環的方法來解決。我們只需要確定在總部數中哪些步數右行或是哪些步數下行即可知道其對應的路徑。這里運用到排列組合的思想。 題目要求 A robot is located at the top-left corner of a m x n grid (marked Start in ...
閱讀 2604·2021-11-02 14:39
閱讀 4322·2021-10-11 10:58
閱讀 1446·2021-09-06 15:12
閱讀 1837·2021-09-01 10:49
閱讀 1326·2019-08-29 18:31
閱讀 1882·2019-08-29 16:10
閱讀 3331·2019-08-28 18:21
閱讀 867·2019-08-26 10:42