Given a N x N matrix mat[][] consisting of non-negative integers, the task is to find the number of ways to reach a given score M starting from the cell (0, 0) and reaching the cell (N – 1, N – 1) by going only down(from (i, j) to (i + 1, j)) or right(from (i, j) to (i, j + 1)). Whenever a cell (i, j) is reached, total score is updated by currentScore + mat[i][j].
Examples:
Input: mat[][] = {{1, 1, 1},
{1, 1, 1},
{1, 1, 1}}, M = 4
Output: 0
All the paths will result in a score of 5.
Input: mat[][] = {{1, 1, 1},
{1, 1, 1},
{1, 1, 1}}, M = 5
Output: 6
Approach: This problem can be solved using dynamic programming. First, we need to decide the states of the DP. For every cell (i, j) and a number 0 ? X ? M, we will store the number of ways to reach that cell from the cell (0, 0) with a total score of X. Thus, our solution will use 3-dimensional dynamic programming, two for the coordinates of the cells and one for the required score value.
The required recurrence relation will be,
dp[i][j][M] = dp[i – 1][j][M – mat[i][j]] + dp[i][j-1][M – mat[i][j]]
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <iostream> using namespace std; #define n 3 #define MAX 30 // To store the states of dp int dp[n][n][MAX]; // To check whether a particular state // of dp has been solved bool v[n][n][MAX]; // Function to find the ways // using memoization int findCount( int mat[][n], int i, int j, int m) { // Base cases if (i == 0 && j == 0) { if (m == mat[0][0]) return 1; else return 0; } // If required score becomes negative if (m < 0) return 0; if (i < 0 || j < 0) return 0; // If current state has been reached before if (v[i][j][m]) return dp[i][j][m]; // Set current state to visited v[i][j][m] = true ; dp[i][j][m] = findCount(mat, i - 1, j, m - mat[i][j]) + findCount(mat, i, j - 1, m - mat[i][j]); return dp[i][j][m]; } // Driver code int main() { int mat[n][n] = { { 1, 1, 1 }, { 1, 1, 1 }, { 1, 1, 1 } }; int m = 5; cout << findCount(mat, n - 1, n - 1, m); return 0; } |
Java
// Java implementation of the approach class GFG { static int n = 3 ; static int MAX = 30 ; // To store the states of dp static int dp[][][] = new int [n][n][MAX]; // To check whether a particular state // of dp has been solved static boolean v[][][] = new boolean [n][n][MAX]; // Function to find the ways // using memoization static int findCount( int mat[][], int i, int j, int m) { // Base cases if (i == 0 && j == 0 ) { if (m == mat[ 0 ][ 0 ]) return 1 ; else return 0 ; } // If required score becomes negative if (m < 0 ) return 0 ; if (i < 0 || j < 0 ) return 0 ; // If current state has been reached before if (v[i][j][m]) return dp[i][j][m]; // Set current state to visited v[i][j][m] = true ; dp[i][j][m] = findCount(mat, i - 1 , j, m - mat[i][j]) + findCount(mat, i, j - 1 , m - mat[i][j]); return dp[i][j][m]; } // Driver code public static void main(String[] args) { int mat[][] = { { 1 , 1 , 1 }, { 1 , 1 , 1 }, { 1 , 1 , 1 } }; int m = 5 ; System.out.println(findCount(mat, n - 1 , n - 1 , m)); } } /* This code contributed by PrinciRaj1992 */ |
Python3
# Python3 implementation of the approach n = 3 MAX = 60 # To store the states of dp dp = [[[ 0 for i in range ( 30 )] for i in range ( 30 )] for i in range ( MAX + 1 )] # To check whether a particular state # of dp has been solved v = [[[ 0 for i in range ( 30 )] for i in range ( 30 )] for i in range ( MAX + 1 )] # Function to find the ways # using memoization def findCount(mat, i, j, m): # Base cases if (i = = 0 and j = = 0 ): if (m = = mat[ 0 ][ 0 ]): return 1 else : return 0 # If required score becomes negative if (m < 0 ): return 0 if (i < 0 or j < 0 ): return 0 # If current state has been reached before if (v[i][j][m] > 0 ): return dp[i][j][m] # Set current state to visited v[i][j][m] = True dp[i][j][m] = (findCount(mat, i - 1 , j, m - mat[i][j]) + findCount(mat, i, j - 1 , m - mat[i][j])) return dp[i][j][m] # Driver code mat = [ [ 1 , 1 , 1 ], [ 1 , 1 , 1 ], [ 1 , 1 , 1 ] ] m = 5 print (findCount(mat, n - 1 , n - 1 , m)) # This code is contributed by mohit kumar |
C#
// C# implementation of the approach using System; class GFG { static int n = 3; static int MAX = 30; // To store the states of dp static int [,,]dp = new int [n, n, MAX]; // To check whether a particular state // of dp has been solved static bool [,,]v = new bool [n, n, MAX]; // Function to find the ways // using memoization static int findCount( int [,]mat, int i, int j, int m) { // Base cases if (i == 0 && j == 0) { if (m == mat[0, 0]) return 1; else return 0; } // If required score becomes negative if (m < 0) return 0; if (i < 0 || j < 0) return 0; // If current state has been reached before if (v[i, j, m]) return dp[i, j, m]; // Set current state to visited v[i, j, m] = true ; dp[i, j, m] = findCount(mat, i - 1, j, m - mat[i, j]) + findCount(mat, i, j - 1, m - mat[i, j]); return dp[i, j, m]; } // Driver code public static void Main() { int [,]mat = {{ 1, 1, 1 }, { 1, 1, 1 }, { 1, 1, 1 }}; int m = 5; Console.WriteLine(findCount(mat, n - 1, n - 1, m)); } } // This code is contributed by Ryuga |
PHP
<?php // PHP implementation of the approach $n = 3; $MAX = 30; // To store the states of dp $dp = array ( $n , $n , $MAX ); // To check whether a particular state // of dp has been solved $v = array ( $n , $n , $MAX ); // Function to find the ways // using memoization function findCount( $mat , $i , $j , $m ) { // Base cases if ( $i == 0 && $j == 0) { if ( $m == $mat [0][0]) return 1; else return 0; } // If required score becomes negative if ( $m < 0) return 0; if ( $i < 0 || $j < 0) return 0; // If current state has been reached before if ( $v [ $i ][ $j ][ $m ]) return $dp [ $i ][ $j ][ $m ]; // Set current state to visited $v [ $i ][ $j ][ $m ] = true; $dp [ $i ][ $j ][ $m ] = findCount( $mat , $i - 1, $j , $m - $mat [ $i ][ $j ]) + findCount( $mat , $i , $j - 1, $m - $mat [ $i ][ $j ]); return $dp [ $i ][ $j ][ $m ]; } // Driver code $mat = array ( array (1, 1, 1 ), array (1, 1, 1 ), array (1, 1, 1 )); $m = 5; echo (findCount( $mat , $n - 1, $n - 1, $m )); // This code contributed by Code_Mech |
Javascript
<script> // Javascript implementation of the approach var n = 3; var MAX = 30; // To store the states of dp var dp = Array(n); for ( var i =0; i<n; i++) { dp[i] = Array(n); for ( var j=0; j<n; j++) { dp[i][j]=Array(MAX); } } // To check whether a particular state // of dp has been solved var v = Array(n); for ( var i =0; i<n; i++) { v[i] = Array(n); for ( var j=0; j<n; j++) { v[i][j]=Array(MAX); } } // Function to find the ways // using memoization function findCount(mat, i, j, m) { // Base cases if (i == 0 && j == 0) { if (m == mat[0][0]) return 1; else return 0; } // If required score becomes negative if (m < 0) return 0; if (i < 0 || j < 0) return 0; // If current state has been reached before if (v[i][j][m]) return dp[i][j][m]; // Set current state to visited v[i][j][m] = true ; dp[i][j][m] = findCount(mat, i - 1, j, m - mat[i][j]) + findCount(mat, i, j - 1, m - mat[i][j]); return dp[i][j][m]; } // Driver code var mat = [ [ 1, 1, 1 ], [ 1, 1, 1 ], [ 1, 1, 1 ] ]; var m = 5; document.write( findCount(mat, n - 1, n - 1, m)); </script> |
6
Time complexity: O(N * N * M)
Auxiliary Space: O(N * N * MAX)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!