ТЕМА 15

//ТЕМА_15//

public class UASD_2_220221{
    //START OF MAIN//
    public static void main(String args[]){
        System.out.println(numberOfPaths(9, 9)); //INPUT NxM//
    }//END OF MAIN//

    //START OF CLASS//
    static int numberOfPaths(int m, int n){
        int[] dp = new int[n];//USING 1 DIMENSIONAL ARRAY TO STORE THE RESULTS WE ALREADY KNOW//
        dp[0] = 1;

        //i-FOR THE COLONS | j-FOR THE ROWS//
        for (int i = 0; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[j] += dp[j - 1];
            }
        }
        System.out.print("The number of possible paths is: " );
        return dp[n - 1];
    }//END OF CLASS//
}

/*------------------------------TESTS------------------------------
                                3x3 ----> 6 Possible paths
                                5x5 ----> 70 Possible paths
                                9x9 ----> 12870 Possible paths
                                15x15 ----> 40116600 Possible path
                                3x2 ----> 3 Possible paths
                                                                 */