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

สมมติว่าเรามีเมทริกซ์ไบนารีขนาด N x M โดย 0 = ช่องว่าง, 1 = ช่องบล็อก เริ่มจากมุมซ้ายบน (0,0) ต้องการหาจำนวนวิธีเดินไปมุมขวาล่าง (N-1, M-1) เดินได้เฉพาะขวาและล่าง ถ้าคำตอบมากเกินไป ให้ modulo 10^9+7

เช่น เมทริกซ์:

0 0 1
0 0 0
1 1 0

ขั้นตอนการแก้ปัญหา (Dynamic Programming)

• dp := matrix ขนาดเดียวกัน เติม 0, dp[0][0] = 1
• เติมคอลัมน์แรก: ถ้า matrix[i][0] == 1 หยุด, มิฉะนั้น dp[i][0] = 1
• เติมแถวแรก: ถ้า matrix[0][j] == 1 หยุด, มิฉะนั้น dp[0][j] = 1
• วน i=1..n-1, j=1..m-1:
  • ถ้า matrix[i][j] == 1: dp[i][j] = 0
  • มิฉะนั้น: dp[i][j] = dp[i-1][j] + dp[i][j-1]
• คืน dp[-1][-1]

ตัวอย่างโค้ด

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