In this tutorial, we will learn about the total number of decreasing paths in a matrix in Java. An intriguing task in matrix traversal is to identify and count decreasing paths. A sequence of adjacent cells with values fewer than those of the paths' bordering cells makes up a matrix's decreasing route. These routes might be significant for uses when a continuous descent in altitude is required, like topographic analysis. The total number of decreasing routes in a matrix can be found using dynamic programming.

Examples:

Example 1:

Input : m[][] = { { 1, 2 }, { 1, 3 } }
Output : 8
Explanation : Paths that are getting shorter are { 1 }, { 1 }, { 2 }, { 3 }, { 2, 1 }, { 3, 1 }, { 3, 2 }, { 3, 2, 1 }

Example 2:
Input : m[][] = { { 1, 2, 3 },{ 1, 3, 4 },{ 1, 5, 6 } }

Output : 41

Approach: Using Dynamic Programming

The approach quickly finds the total number of decreasing paths in the provided matrix by using recursion and dynamic programming.
The best way to handle this issue is to apply techniques from dynamic programming. Big issues can be divided into smaller ones that only need to be solved once with the use of dynamic programming. Once that is done, the solutions can be kept for subsequent use. Dynamic programming can be used to count the total number of decreasing paths originating from each matrix cell, which will help choose the best whole-problem approach.

Step 1: Count the number of descending routes in each cell and create a 2D array called dp[][, which should be n × n. Set the initial value of dp[][] to -1 for each element.

Step 2: Make the recursive function CountDecreasingPathsCell (mat, dp, n, x, y):

Step 2.1: Return dp[x][y], if dp[x][y] does not equal -1.

Step 2.2: Set ans to 1 at first.

Step 2.3: Each cell (newx, newy) adjacent to (x, y):

Step 2.4: Add the response to dp[x][y]. When (newx, newy) is inside boundaries

and mat[newx][newy] < mat[x][y], then x Return ans.

Step 3: Create a 2D array called dp[][], with n x n dimensions, and set the initial value of each element to -1.

Step 3.1: Initialize a variable's sum to zero.

Step 3.2: Regarding each matrix cell (i, j):

append the outcome of CountDecreasingPathsCell(mat, dp, n, i, j).
Step 3.3: Return the total.

Step 4: Describe the matrix input. Give countDecreasingPathsMatrix a call (n, mat). print the result.

Filename: DecreasingPaths.java

import java.util.*;

import java.lang.*;

import java.io.*;

public class DecreasingPaths

{ 

// Function that returns the number of

// decreasing paths from a cell(i, j)

public static int CountDecreasingPathsCell(int mat[][], int dp[][],

                                           int n, int x, int y)

    {

        // checking if already calculated

        if (dp[x][y] != -1)

            return dp[x][y];

        // all possible paths

        int delta[][] = { { 0, 1 }, { 1, 0 },

                          { -1, 0}, { 0, -1}};

        int newx, newy;

        // counts the total

        // number of paths

        int ans = 1;

        // In all four allowed direction.

        for (int i = 0; i < 4; i++)

        {

            // new co-ordinates

            newx = x + delta[i][0];

            newy = y + delta[i][1];

            // Checking if not going out

            // of matrix and next cell

            // value is less than current

            // cell value.

            if (newx >= 0 && newx < n && newy >= 0 &&

                newy < n && mat[newx][newy] < mat[x][y])

            {

                ans += CountDecreasingPathsCell(mat, dp, n,

                                                newx, newy);

            }

        }

        // function that

        // returns the answer

        return dp[x][y] = ans;

    }

// Function that counts the total

// decreasing path in the matrix

public static int countDecreasingPathsMatrix(int n,

                                             int mat[][])

    {

        int dp[][] = new int[n][n];

        // Initialising dp[][] to -1.

        for (int i = 0; i < n; i++)

            for (int j = 0; j < n; j++)

                dp[i][j] = -1;

        int sum = 0;

        // Calculating number of

        // decreasing path from each cell.

        for (int i = 0; i < n; i++)

            for (int j = 0; j < n; j++)

                sum += CountDecreasingPathsCell(mat, dp,

                                                n, i, j);

        return sum;

    }

// Driver Code

public static void main(String[] args)

{

    int n = 2;

    int mat[][]= {{1, 2},

                  {1, 3}};

    // function call that returns the

    // count of decreasing paths in a matrix

    System.out.println(countDecreasingPathsMatrix(n, mat));

}

}

Output

Time Complexity : The time complexity of a program is O(N²)

Space Complexity: The space complexity of a program isO(N²)

← Prev Next →

Total Number of Decreasing Paths in a Matrix in Java

Approach: Using Dynamic Programming