Day 37 of 100 days dsa coding challenge

Taking on a new challenge: solving GeeksforGeeks POTD daily and sharing my solutions! 💻🔥
The goal: sharpen problem-solving skills, level up coding, and learn something new every day. Follow my journey! 🚀

100DaysOfCode #CodingChallenge #ProblemSolving #GeeksforGeeks #DeveloperJourney

Problem:

https://www.geeksforgeeks.org/problems/number-of-paths-in-a-matrix-with-k-coins2728/1

Number of paths in a matrix with k coins

Difficulty: Medium Accuracy: 16.96%

You are given a matrix mat[][] of size n x m, where each of its cells contains some coins. Count the number of ways to collect exactly k coins while moving from the top left cell of the matrix to the bottom right cell.
From a cell (i, j), you can only move to cell (i+1, j) or (i, j+1).
Note: It is guaranteed that the answer will not exceed 32-bit integer limits.

Examples:
Input: k = 12, mat[] = [[1, 2, 3],
[4, 6, 5],
[3, 2, 1]]
Output: 2
Explanation: There are 2 possible paths with exactly 12 coins, (1 + 2 + 6 + 2 + 1) and (1 + 2 + 3 + 5 + 1).
Input: k = 16, mat[] = [[1, 2, 3],
[4, 6, 5],
[9, 8, 7]]
Output: 0
Explanation: There are no possible paths that lead to sum = 16.
Constraints:
1 ≤ k ≤ 100
1 ≤ n, m ≤ 100
0 ≤ mat[i][j] ≤ 200

Solution:
class Solution:
def numberOfPath(self, mat, k):
n, m = len(mat), len(mat[0])
dp = [[[0]*(k+1) for _ in range(m)] for _ in range(n)]
if mat[0][0] <= k:
dp[0][0][mat[0][0]] = 1
for i in range(n):
for j in range(m):
for c in range(k+1):
if i > 0 and c >= mat[i][j]:
dp[i][j][c] += dp[i-1][j][c - mat[i][j]]
if j > 0 and c >= mat[i][j]:
dp[i][j][c] += dp[i][j-1][c - mat[i][j]]
return dp[n-1][m-1][k]