পাইথনে নির্দিষ্ট খরচ বিশিষ্ট পথের সংখ্যা গণনার প্রোগ্রাম

ধরুন আমাদের একটি ২D বাইনারি ম্যাট্রিক্স এবং একটি মান k দেওয়া আছে। উপরের বাম কোণ থেকে শুরু করে নিচের ডান কোণে যেতে হবে। প্রতিটি ধাপে শুধু নিচে বা ডানে যাওয়া যাবে। একটি পথের স্কোর হল সেই পথে পড়া সেলগুলোর মানগুলোর যোগফল। স্কোর ঠিক k হওয়া পথগুলোর সংখ্যা বের করতে হবে। যদি সংখ্যা খুব বেশি হয়, তবে 10^9+7 দিয়ে ভাগশেষ ফেরত দিন।

উদাহরণস্বরূপ, ইনপুট ম্যাট্রিক্স:

0	0	1
1	0	1
0	1	0

K = 2 হলে আউটপুট হবে 4।

সমাধানের ধাপসমূহ

deno := 10^9 + 7
m, n := len(matrix), len(matrix[0])
dfs(i, j, pts) ফাংশন সংজ্ঞায়িত করুন:
- যদি i >= m or j >= n, তবে 0 ফেরত দিন
- pts += matrix[i][j]
- যদি i == m-1 and j == n-1, তবে 1 if pts == k else 0 ফেরত দিন
- dfs(i+1, j, pts) + dfs(i, j+1, pts) ফেরত দিন
মূল পদ্ধতিতে dfs(0, 0, 0) % deno ফেরত দিন

উদাহরণ

class Solution:
    def solve(self, matrix, k):
        m, n = len(matrix), len(matrix[0])
        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)
        return dfs() % (10 ** 9 + 7)

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

ইনপুট

[[0, 0, 1], [1, 0, 1], [0, 1, 0]], 2