Count number of ways to reach a given score in a Matrix
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 dpint dp[n][n][MAX];// To check whether a particular state// of dp has been solvedbool v[n][n][MAX];// Function to find the ways// using memoizationint 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 codeint 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 approachclass GFG{static int n = 3;static int MAX =30;// To store the states of dpstatic int dp[][][] = new int[n][n][MAX];// To check whether a particular state// of dp has been solvedstatic boolean v[][][] = new boolean[n][n][MAX];// Function to find the ways// using memoizationstatic 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 codepublic 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 approachn = 3MAX = 60# To store the states of dpdp = [[[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 solvedv = [[[0 for i in range(30)] for i in range(30)] for i in range(MAX + 1)]# Function to find the ways# using memoizationdef 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 codemat = [ [ 1, 1, 1 ], [ 1, 1, 1 ], [ 1, 1, 1 ] ]m = 5print(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 memoizationfunction 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 approachvar n = 3;var MAX = 30;// To store the states of dpvar 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 solvedvar 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 memoizationfunction 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 codevar mat = [ [ 1, 1, 1 ], [ 1, 1, 1 ], [ 1, 1, 1 ] ];var m = 5;document.write( findCount(mat, n - 1, n - 1, m));</script> |
Output:
6
Time complexity: O(N * N * M)
Auxiliary Space: O(N * N * MAX)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!
