程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> LeetCode Unique Paths

LeetCode Unique Paths

編輯:關於C++

LeetCode解題之Unique Paths


原題

機器人從起點到終點有多少條不同的路徑,只能向右或者向下走。

unique-path

注意點:<喎?/kf/ware/vc/" target="_blank" class="keylink">vcD4NCrjx19O089Ch1+60886qMTAwKjEwMA0KPHA+wP3X06O6PC9wPg0KPHA+yuTI6zogbSA9IDMsIG4gPSA3PC9wPg0KPHA+yuSz9jogMjg8L3A+DQo8aDIgaWQ9"解題思路">解題思路

很常見的小學生奧數題,可以用排列組合來求解,一共要走(m-1)+(n-1)步,其中(m-1)步向下,(n-1)向右,且有公式 mCn = n!/m!(n-m)! ,那麼可以用下面的代碼求解:

import math
class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        m -= 1
        n -= 1
        return math.factorial(m+n) / (math.factorial(n) * math.factorial(m))

當然了,更常見的一種做法就是動態規劃,要到達一個格子只有從它上面或者左邊的格子走過來,遞推關系式:dp[i][j]=dp[i-1][j]+dp[i][j-1]。初始化條件是左邊和上邊都只有一條路徑,索性在初始化時把所有格子初始化為1。

AC源碼

class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        dp = [[1 for __ in range(n)] for __ in range(m)]
        for i in range(1, n):
            for j in range(1, m):
                dp[j][i] = dp[j - 1][i] + dp[j][i - 1]
        return dp[m - 1][n - 1]


if __name__ == "__main__":
    assert Solution().uniquePaths(3, 7) == 28
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved