Untitled

public class NumberOfIncreasingPaths {

    private static final int MOD = 1_000_000_007;

    public static int countIncreasingPaths(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] memo = new int[m][n]; // Memoization array to store results
        int totalPaths = 0;

        // Iterate over all cells to count all increasing paths
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                totalPaths = (totalPaths + dfs(matrix, i, j, memo)) % MOD;
            }
        }

        return totalPaths;
    }

    private static int dfs(int[][] matrix, int row, int col, int[][] memo) {
        // If already computed, return the memoized result
        if (memo[row][col] != 0) {
            return memo[row][col];
        }

        int m = matrix.length;
        int n = matrix[0].length;
        int pathCount = 1; // Count the path starting from the current cell

        // Directions: up, down, left, right
        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        for (int[] dir : directions) {
            int newRow = row + dir[0];
            int newCol = col + dir[1];

            // Move to the new cell if it's within bounds and greater than the current cell
            if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && matrix[newRow][newCol] > matrix[row][col]) {
                pathCount = (pathCount + dfs(matrix, newRow, newCol, memo)) % MOD;
            }
        }

        // Store the result in the memoization array
        memo[row][col] = pathCount;

        return pathCount;
    }

    public static void main(String[] args) {
        int[][] matrix1 = {{1, 2}, {3, 4}};
        System.out.println(countIncreasingPaths(matrix1)); // Output: 10

        int[][] matrix2 = {{9, 9, 4}, {6, 6, 8}, {2, 1, 1}};
        System.out.println(countIncreasingPaths(matrix2)); // Output: 21

        int[][] matrix3 = {{3, 4, 5}, {3, 2, 6}, {2, 2, 1}};
        System.out.println(countIncreasingPaths(matrix3)); // Output: 21
    }
}