โปรแกรมหาจำนวนวิธีที่เราสามารถเข้าถึงได้จากจุดบนซ้ายไปยังจุดล่างขวาใน Python

สมมติว่าเรามีเมทริกซ์ไบนารี N x M หนึ่งตัว โดยที่ 0 หมายถึงเซลล์ว่างและ 1 หมายถึงเซลล์ที่ถูกบล็อก เริ่มจากมุมซ้ายบน ต้องหาหลายวิธีที่จะไปถึงมุมขวาล่าง หากคำตอบมีขนาดใหญ่มาก ให้แก้ไข 10^9 + 7

ดังนั้นหากอินพุตเป็นแบบ

จากนั้นผลลัพธ์จะเป็น 2 เนื่องจากมีสองวิธีในการไปที่ด้านล่างขวา:[Right, Down, Right, Down] และ [Down, Right, Right, Down].

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• dp :=เมทริกซ์ที่มีขนาดเท่ากันกับเมทริกซ์ที่กำหนดและเติมด้วย 0
• dp[0, 0] :=1
• สำหรับ i ในช่วง 1 ถึงแถวนับของเมทริกซ์ ทำ
  • ถ้า matrix[i, 0] เหมือนกับ 1 แล้ว
    • ออกมาจากลูป
  • มิฉะนั้น
    • dp[i, 0] :=1
• สำหรับ j ในช่วง 1 ถึงจำนวนคอลัมน์ของเมทริกซ์ ให้ทำ
  • ถ้าเมทริกซ์[0, j] เหมือนกับ 1 แล้ว
    • ออกมาจากวงจร
  • มิฉะนั้น
    • dp[0, j] :=1
• สำหรับ i ในช่วง 1 ถึงแถวนับของเมทริกซ์ ทำ
  • สำหรับ j ในช่วง 1 ถึงจำนวนคอลัมน์ของเมทริกซ์ ให้ทำ
    • ถ้า matrix[i, j] เหมือนกับ 1 แล้ว
      • dp[i, j] :=0
    • มิฉะนั้น
      • dp[i, j] :=dp[i - 1, j] + dp[i, j - 1]
• คืนค่าด้านล่างขวาของ dp

ตัวอย่าง (Python)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

class Solution:
   def solve(self, matrix):
      dp = [[0] * len(matrix[0]) for _ in range(len(matrix))]
      dp[0][0] = 1
      for i in range(1, len(matrix)):
         if matrix[i][0] == 1:
            break
         else:
            dp[i][0] = 1
      for j in range(1, len(matrix[0])):
         if matrix[0][j] == 1:
            break
         else:
            dp[0][j] = 1
      for i in range(1, len(matrix)):
         for j in range(1, len(matrix[0])):
            if matrix[i][j] == 1:
               dp[i][j] = 0
            else:
               dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
      return dp[-1][-1]
ob = Solution()
matrix = [
   [0, 0, 1],
   [0, 0, 0],
   [1, 1, 0]
]
print(ob.solve(matrix))

อินพุต

matrix = [
[0, 0, 1],
[0, 0, 0],
[1, 1, 0] ]

ผลลัพธ์

2