leetcode中如何解決不同路徑問(wèn)題

小編給大家分享一下leetcode中如何解決不同路徑問(wèn)題，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！

創(chuàng)新互聯(lián)公司是專(zhuān)業(yè)的江城網(wǎng)站建設(shè)公司，江城接單;提供網(wǎng)站建設(shè)、成都網(wǎng)站設(shè)計(jì),網(wǎng)頁(yè)設(shè)計(jì),網(wǎng)站設(shè)計(jì),建網(wǎng)站,PHP網(wǎng)站建設(shè)等專(zhuān)業(yè)做網(wǎng)站服務(wù);采用PHP框架,可快速的進(jìn)行江城網(wǎng)站開(kāi)發(fā)網(wǎng)頁(yè)制作和功能擴(kuò)展;專(zhuān)業(yè)做搜索引擎喜愛(ài)的網(wǎng)站,專(zhuān)業(yè)的做網(wǎng)站團(tuán)隊(duì),希望更多企業(yè)前來(lái)合作!

一個(gè)機(jī)器人位于一個(gè) m x n 網(wǎng)格的左上角 （起始點(diǎn)在下圖中標(biāo)記為“Start” ）。

機(jī)器人每次只能向下或者向右移動(dòng)一步。機(jī)器人試圖達(dá)到網(wǎng)格的右下角（在下圖中標(biāo)記為“Finish”）。

問(wèn)總共有多少條不同的路徑？

例如，上圖是一個(gè)7 x 3 的網(wǎng)格。有多少可能的路徑？

說(shuō)明：m 和 n 的值均不超過(guò) 100。

示例 1:

輸入: m = 3, n = 2

輸出: 3

解釋:

從左上角開(kāi)始，總共有 3 條路徑可以到達(dá)右下角。

1. 向右 -> 向右 -> 向下

2. 向右 -> 向下 -> 向右

3. 向下 -> 向右 -> 向右

示例 2:

輸入: m = 7, n = 3

輸出: 28

解題思路：

1，這個(gè)問(wèn)題可以拆解成子問(wèn)題，并且可以用子問(wèn)題的結(jié)果來(lái)求最終結(jié)果，典型的動(dòng)態(tài)規(guī)劃

2，step[i,j]路徑數(shù)＝step[i,j-1] +step[i-1,j]

3,用到了i-1,j-1;所以用遞增的方式

代碼

func uniquePaths(m int, n int) int {    step:=make([][]int,m)    for i:=0;i<m;i++{        step[i]=make([]int,n)        step[i][0]=1    }    for i:=0;i<n;i++{        step[0][i]=1    }    for i:=1;i<m;i++{        for j:=1;j<n;j++{            step[i][j]=step[i-1][j]+step[i][j-1]        }    }    return step [m-1][n-1]}

以上是“l(fā)eetcode中如何解決不同路徑問(wèn)題”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對(duì)大家有所幫助，如果還想學(xué)習(xí)更多知識(shí)，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道！

網(wǎng)頁(yè)題目：leetcode中如何解決不同路徑問(wèn)題
網(wǎng)址分享：http://muchs.cn/article20/ighejo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供面包屑導(dǎo)航、網(wǎng)站設(shè)計(jì)、網(wǎng)站策劃、App開(kāi)發(fā)、用戶(hù)體驗(yàn)、電子商務(wù)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶(hù)投稿、用戶(hù)轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)