Question:

How to check a number of paths in a matrix with k coins using C++

Summary

Here we have to find the number of paths in an nXn grid, where each cell has a certain value associated with it. Plus, the sum of values along the path equals a given value k.

Assuming two functions ‘solve’, and ‘numberofpaths’.

Solution

class Solution {

public:

long long solve(int i, int j, int n, int k, vector<vector<int>> &arr, long long col, vector<vector<vector<long long>>> &dp) {

// Check if out of bounds or exceeded k

if (i >= n || j >= n || col > k) {

return 0;

}

if(dp[i][j][col]!=-1)return dp[i][j][col];

// col += arr[i][j];

if (i == n - 1 && j == n - 1 ) {

if(col+arr[i][j]==k)

return 1;

return 0;

}

// Recursively explore the down and right directions

long long a1 = solve(i + 1, j, n, k, arr, col+arr[i][j],dp);

long long a2 = solve(i, j + 1, n, k, arr, col+arr[i][j],dp);

return dp[i][j][col]=a1 + a2;

}

long long numberOfPath(int n, int k, vector<vector<int>> &arr) {

long long a = 0;

vector<vector<vector<long long>>> dp;

dp.resize(n, vector<vector<long long>>(n, vector<long long>(k + 1, -1)));

long long ans = solve(0, 0, n, k, arr, a,dp);

return ans;

}

Explanation

solve

This function is a recursive helper function that explores possible paths starting from cell.

numberOfPath function

This function initializes the memoization vector dp and then calls the solve function to find the number of paths from the top-left corner to the bottom-right corner with the given constraints.