Chương trình đếm số đường đi có chi phí k từ đầu đến cuối ma trận trong Python

Cho ma trận nhị phân và giá trị k. Từ ô (0,0) đi đến (m-1,n-1) chỉ được đi xuống hoặc phải. Điểm của đường đi = tổng giá trị các ô trên đường. Đếm số đường đi có điểm = k. Kết quả modulo 10^9+7.

Ví dụ ma trận 3x3, k=2 → kết quả 4 (4 đường đi: RRDD, DRRD, DDRR, DRDR).

Giải thuật (DFS đệ quy)

1. Hàm dfs(i, j, pts) trả về số đường từ (i,j) với điểm tích lũy pts.
2. Nếu vượt biên → 0.
3. Cộng matrix[i][j] vào pts.
4. Nếu đến đích → trả về 1 nếu pts == k else 0.
5. Đệ quy: dfs(i+1, j, pts) + dfs(i, j+1, pts).

Lưu ý: Giải pháp này chưa dùng memoization, có thể tối ưu bằng DP 3 chiều.

Ví dụ minh họa

class Solution:
    def solve(self, matrix, k):
        m, n = len(matrix), len(matrix[0])
        MOD = 10**9 + 7
        
        def dfs(i=0, j=0, pts=0):
            if i >= m or j >= n:
                return 0
            pts += matrix[i][j]
            if i == m - 1 and j == n - 1:
                return int(pts == k)
            return (dfs(i + 1, j, pts) + dfs(i, j + 1, pts)) % MOD
        
        return dfs()

ob = Solution()
matrix = [[0,0,1],[1,0,1],[0,1,0]]
k = 2
print(ob.solve(matrix, k))  # Output: 4

Đầu vào / Đầu ra

Input: [[0,0,1],[1,0,1],[0,1,0]], 2

Output: 4