日本综合一区二区|亚洲中文天堂综合|日韩欧美自拍一区|男女精品天堂一区|欧美自拍第6页亚洲成人精品一区|亚洲黄色天堂一区二区成人|超碰91偷拍第一页|日韩av夜夜嗨中文字幕|久久蜜综合视频官网|精美人妻一区二区三区

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

新聞中心

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

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

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

題目說明

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

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

問總共有多少條不同的路徑?

圖片來源leetcode

示例1:

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

示例2:

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

提示：

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

解題思路

利用動態(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)前位置：

向下：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]

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

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

說明，從f[0][0]出發(fā)，那么開始時，節(jié)點f[0][0]=1，

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

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

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

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

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

代碼實現(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 { //可以向下，向右移動
    10. 
  
  
  
  
  10. 10                f[i][j] = f[i-1][j] + f[i][j-1]
    11. 
  
  
  
  
  11. 11            }else if i>0 { //可以向下移動
    12. 
  
  
  
  
  12. 12                f[i][j] = f[i-1][j]
    13. 
  
  
  
  
  13. 13            }else if j>0 { //可以向右移動
    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é)束后，走到了終點
    19. 
  
  
  
  
  19. 19    return f[m-1][n-1]
    20. 
  
  
  
  
  20. 20}
    21.

復(fù)雜度分析

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

分享文章：一篇搞定動態(tài)規(guī)劃之不同路徑
當(dāng)前網(wǎng)址：http://www.dlmjj.cn/article/djeooeg.html