ได้รับเมทริกซ์ไบนารี 2D และค่า k เริ่มจากมุมซ้ายบน (0,0) ไปมุมขวาล่าง (m-1,n-1) เดินได้เฉพาะ ขวา หรือ ลง คะแนนเส้นทาง = ผลรวมค่าเซลล์ที่ผ่าน หาจำนวนเส้นทางที่มีคะแนนเท่ากับ k (mod 10^9+7)
ตัวอย่าง
0 0 1 1 0 1 0 1 0
k = 2 → Output: 4
เส้นทาง: RRDD, RDRD, DRRD, DDRR (R=ขวา, D=ลง)
แนวทางแก้ปัญหา
DP 3 มิติ หรือ Memoized DFS:
- State:
dp(i, j, sum)= จำนวนวิธีจาก(i,j)ไปปลายทางด้วยผลรวมสะสมsum - Base: ถ้าถึงปลายทาง → คืน 1 ถ้า
sum == kไม่งั้น 0 - Transition:
dp(i,j,sum) = dp(i+1,j,sum+mat[i][j]) + dp(i,j+1,sum+mat[i][j])
หมายเหตุ: รุ่นต้นฉบับใช้ recursion แบบไม่มี memoization จะช้ามากสำหรับเมทริกซ์ใหญ่ ควรเพิ่ม lru_cache หรือใช้ bottom-up DP
การใช้งาน (Python - แบบ Memoized)
from functools import lru_cache
class Solution:
def solve(self, matrix, k):
m, n = len(matrix), len(matrix[0])
MOD = 10**9 + 7
@lru_cache(None)
def dfs(i, j, pts):
if i >= m or j >= n:
return 0
pts += matrix[i][j]
if i == m - 1 and j == n - 1:
return 1 if pts == k else 0
return (dfs(i + 1, j, pts) + dfs(i, j + 1, pts)) % MOD
return dfs(0, 0, 0)
# ทดสอบ
ob = Solution()
matrix = [[0,0,1], [1,0,1], [0,1,0]]
print(ob.solve(matrix, 2)) # Output: 4
ความซับซ้อน
- Time Complexity: O(m × n × k)
- Space Complexity: O(m × n × k)
