10. Number of paths in a matrix with k coins

The problem can be found at the following link:

My Approach

Initialization:

Define movement directions: dr[]={1, 0} and dc[]={0, 1}.
Use lambda function valid to check matrix boundaries.

Dynamic Programming Setup:

Initialize a 3D DP array dp of size n x n x k+1 with -1.

Recursive Helper Function:

Define helper(r, c, sum) to calculate ways.
Base Case:
- If at bottom right, return 1 if sum equals coins, else return 0.
If DP array has a value, return it.
Initialize dp[r][c][sum] to 0.
If coins at current cell <= sum:
- Iterate over directions, add ways from valid neighbors with reduced sum.

Main Function:

Call helper(0, 0, k).

Time and Auxiliary Space Complexity

Time Complexity: The time complexity of this solution is O(N^3 * K) due to the 3D DP array and the recursion.
Auxiliary Space Complexity: The auxiliary space complexity is O(N^3 * K) due to the 3D DP array.

Code (C++)

class Solution {
public:
    long long numberOfPath(int n, int k, vector<vector<int>> arr)
    {
        int dr[]={1, 0};
        int dc[]={0, 1};
        auto valid=[&](int x, int y)->bool
        {
            if(x<0 || x>=n || y<0 || y>=n)
                return 0;
            return 1;
        };
        vector<vector<vector<long long>>>dp(n, vector<vector<long long>>(n, vector<long long>(k+1, -1)));
        function<long long(int, int, int)>helper=[&](int r, int c, int sum)->long long
        {
            if(r==n-1 and c==n-1)
                return dp[r][c][sum]=sum==arr[r][c];
            if(dp[r][c][sum]!=-1)
                return dp[r][c][sum];
            dp[r][c][sum]=0;
            if(arr[r][c]<=sum)
            {
                for(int dir=0;dir<2;dir++)
                {
                    int nr=r+dr[dir];
                    int nc=c+dc[dir];
                    if(valid(nr, nc))
                        dp[r][c][sum]+=helper(nr, nc, sum-arr[r][c]);
                }            
            }
            return dp[r][c][sum];
        };
        return helper(0, 0, k);
    }
    
};

Contribution and Support

Previous02-2024(feb)Next02-2024(feb)

Last updated 1 year ago

Was this helpful?

My Approach

Initialization:

Define movement directions: dr[]={1, 0} and dc[]={0, 1}.

Use lambda function valid to check matrix boundaries.

Dynamic Programming Setup:

Initialize a 3D DP array dp of size n x n x k+1 with -1.

Recursive Helper Function:

Define helper(r, c, sum) to calculate ways.

Base Case:

If at bottom right, return 1 if sum equals coins, else return 0.

If DP array has a value, return it.

Initialize dp[r][c][sum] to 0.

If coins at current cell <= sum:

Iterate over directions, add ways from valid neighbors with reduced sum.

Main Function:

Call helper(0, 0, k).

Code (C++)

class Solution {
public:
    long long numberOfPath(int n, int k, vector<vector<int>> arr)
    {
        int dr[]={1, 0};
        int dc[]={0, 1};
        auto valid=[&](int x, int y)->bool
        {
            if(x<0 || x>=n || y<0 || y>=n)
                return 0;
            return 1;
        };
        vector<vector<vector<long long>>>dp(n, vector<vector<long long>>(n, vector<long long>(k+1, -1)));
        function<long long(int, int, int)>helper=[&](int r, int c, int sum)->long long
        {
            if(r==n-1 and c==n-1)
                return dp[r][c][sum]=sum==arr[r][c];
            if(dp[r][c][sum]!=-1)
                return dp[r][c][sum];
            dp[r][c][sum]=0;
            if(arr[r][c]<=sum)
            {
                for(int dir=0;dir<2;dir++)
                {
                    int nr=r+dr[dir];
                    int nc=c+dc[dir];
                    if(valid(nr, nc))
                        dp[r][c][sum]+=helper(nr, nc, sum-arr[r][c]);
                }            
            }
            return dp[r][c][sum];
        };
        return helper(0, 0, k);
    }
    
};