分享

[leetcode補完計畫] 62. Unique Paths (Medium)

leetcode 62 Unique Paths c++ 程式

題目敘述:

給定一個mxn的長方形圖,機器人在左上角,終點在右下角,機器人只能往右或往下,請問總共有幾種方法到達終點。

解題思路:


訂定狀態轉移方程:
使用dp,dp[i][j]代表到達(i, j)格的方法數,要到達這格必定是由上往下,或是由左往右到達,所以狀態轉移方程為
  

dp[i][j] = dp[i-1][j] + dp[i][j-1]


考慮邊界條件:
  

dp[i][0] = 1, 0<= i < m;  

dp[0][j] = 1, 0<= j < n;

到達第0行的方法數只會有一種,因為無法向上走,同理,到達第0列的方法數也只會有一種,因為無法向左走。

計算複雜度:
總共有mxn個狀態,轉移所花費的時間為O(1),總複雜度為:
  

O(mn)

Run code!!
解答參考code

=================================
覺得還不錯的話麻煩在下方留言讓我知道(^_−)−☆
((可以的話就按個讚吧(*≧ω≦)
有任何問題也都可以在下方留言喔
email:ryanovovo.blogg[email protected]
=================================
#leetcode  #程式 
分類:學習

喜歡程式, 文字, 星星, 耍廢 www.timelog.to/user?id=6991461

評論
上一篇
  • [TECH] Geforce Now體驗心得
  • 下一篇
  • [TECH] Likecoin運作原理簡介
  • 更多文章
    載入中... 沒有更多了