日韩无码专区无码一级三级片|91人人爱网站中日韩无码电影|厨房大战丰满熟妇|AV高清无码在线免费观看|另类AV日韩少妇熟女|中文日本大黄一级黄色片|色情在线视频免费|亚洲成人特黄a片|黄片wwwav色图欧美|欧亚乱色一区二区三区

RELATEED CONSULTING
相關(guān)咨詢(xún)
選擇下列產(chǎn)品馬上在線(xiàn)溝通
服務(wù)時(shí)間：8:30-17:00
你可能遇到了下面的問(wèn)題
關(guān)閉右側(cè)工具欄

新聞中心

這里有您想知道的互聯(lián)網(wǎng)營(yíng)銷(xiāo)解決方案
一篇搞定動(dòng)態(tài)規(guī)劃之不同路徑

本文轉(zhuǎn)載自微信公眾號(hào)「我好困啊」，作者我好困啊。轉(zhuǎn)載本文請(qǐng)聯(lián)系我好困啊公眾號(hào)。

10年的桑珠孜網(wǎng)站建設(shè)經(jīng)驗(yàn)，針對(duì)設(shè)計(jì)、前端、開(kāi)發(fā)、售后、文案、推廣等六對(duì)一服務(wù)，響應(yīng)快，48小時(shí)及時(shí)工作處理。成都全網(wǎng)營(yíng)銷(xiāo)推廣的優(yōu)勢(shì)是能夠根據(jù)用戶(hù)設(shè)備顯示端的尺寸不同，自動(dòng)調(diào)整桑珠孜建站的顯示方式，使網(wǎng)站能夠適用不同顯示終端，在瀏覽器中調(diào)整網(wǎng)站的寬度，無(wú)論在任何一種瀏覽器上瀏覽網(wǎng)站，都能展現(xiàn)優(yōu)雅布局與設(shè)計(jì)，從而大程度地提升瀏覽體驗(yàn)。創(chuàng)新互聯(lián)從事“桑珠孜網(wǎng)站設(shè)計(jì)”,“桑珠孜網(wǎng)站推廣”以來(lái)，每個(gè)客戶(hù)項(xiàng)目都認(rèn)真落實(shí)執(zhí)行。

題目說(shuō)明

一個(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)總共有多少條不同的路徑?

圖片來(lái)源leetcode

示例1:

 
 
 
 
    
  
  
  
  
  1. 輸入：m = 3, n = 7
    2. 
  
  
  
  
  2. 輸出：28
    3.

示例2:

 
 
 
 
    
  
  
  
  
  1. 輸入：m = 3, n = 2
    2. 
  
  
  
  
  2. 輸出：3
    3. 
  
  
  
  
  3. 解釋?zhuān)?/li>
  
  
  
  
  4. 從左上角開(kāi)始，總共有 3 條路徑可以到達(dá)右下角。
    5. 
  
  
  
  
  5. 1. 向右 -> 向下 -> 向下
    6. 
  
  
  
  
  6. 2. 向下 -> 向下 -> 向右
    7. 
  
  
  
  
  7. 3. 向下 -> 向右 -> 向下
    8.

提示：

  • 1 <= m, n <= 100
  • 題目數(shù)據(jù)保證答案小于等于 2 * 109

解題思路

利用動(dòng)態(tài)規(guī)劃算法

1.定義狀態(tài)f[i][j]為到達(dá)(i,j)位置的路徑條數(shù)

2.f[0][0] = 1,那么最終m*n的表格，到達(dá)右下角的路徑條數(shù)即為f[m-1][n-1]中的值

3.每次移動(dòng)情況，如果當(dāng)前位置：

向下：f[i][j] = f[i-1][j]

向右: f[i][j] = f[i][j-1]

向下，向右:f[i][j] = f[i-1][j]+f[i][j-1]

如果你還不理解的話(huà)，觀(guān)看一下流轉(zhuǎn)圖：

以2*2的網(wǎng)格為例

說(shuō)明，從f[0][0]出發(fā)，那么開(kāi)始時(shí)，節(jié)點(diǎn)f[0][0]=1，

節(jié)點(diǎn)f[0][1]只能由于f[0][0]向右移動(dòng)得到,即 f[0][1]=f[0][0]

節(jié)點(diǎn)f[1][0]同理，只能f[0][0]下移得到。即 f[1][0]=f[0][0]

節(jié)點(diǎn)f[1][1]，可以由于f[0][1]向下移動(dòng)，f[1][0]向右移動(dòng)。兩種移動(dòng)方式得到。即：f[1][1] = f[0][1] + f[1][0]

最后，f[m-1][n-1]，右下角的位置即為最終結(jié)果

如果你還不理解的話(huà)，建議你手動(dòng)畫(huà)一下2*3的表格移動(dòng)狀態(tài)的轉(zhuǎn)移過(guò)程。

代碼實(shí)現(xiàn)

 
 
 
 
    
  
  
  
  
  1.  1func uniquePaths(m int, n int) int {
    2. 
  
  
  
  
  2.  2    f := make([][]int,m)
    3. 
  
  
  
  
  3.  3    for i:= range f{
    4. 
  
  
  
  
  4.  4        f[i] = make([]int,n)
    5. 
  
  
  
  
  5.  5    }
    6. 
  
  
  
  
  6.  6    f[0][0] = 1
    7. 
  
  
  
  
  7.  7    for i:=0;i
  
  
  
  
  8.  8        for j:=0;j
  
  
  
  
  9.  9            if i>0 && j>0 { //可以向下，向右移動(dòng)
    10. 
  
  
  
  
  10. 10                f[i][j] = f[i-1][j] + f[i][j-1]
    11. 
  
  
  
  
  11. 11            }else if i>0 { //可以向下移動(dòng)
    12. 
  
  
  
  
  12. 12                f[i][j] = f[i-1][j]
    13. 
  
  
  
  
  13. 13            }else if j>0 { //可以向右移動(dòng)
    14. 
  
  
  
  
  14. 14                f[i][j] = f[i][j-1]
    15. 
  
  
  
  
  15. 15            }
    16. 
  
  
  
  
  16. 16        }
    17. 
  
  
  
  
  17. 17    }
    18. 
  
  
  
  
  18. 18    //循環(huán)結(jié)束后，走到了終點(diǎn)
    19. 
  
  
  
  
  19. 19    return f[m-1][n-1]
    20. 
  
  
  
  
  20. 20}
    21.

復(fù)雜度分析

  • 時(shí)間復(fù)雜度：O(m*n)
  • 空間復(fù)雜度: O(m*n)

網(wǎng)站標(biāo)題：一篇搞定動(dòng)態(tài)規(guī)劃之不同路徑
當(dāng)前鏈接：http://www.5511xx.com/article/djeooeg.html