Untitled

import java.util.Scanner;
class Main {
    // leetcode 62 ================================================
    public int up_rec(int i, int j, int n, int m){
        if(i==n-1 && j==m-1){
            return 1;
        }

        int rightPaths = 0;
        int downPaths = 0;

        if(j+1 < m){
            rightPaths = up_rec(i,j+1,n,m);
        }

        if(i+1 < n){
            downPaths = up_rec(i+1,j,n,m);
        }

        int totalPaths = rightPaths + downPaths;
        return totalPaths;
    }

    public int up_memo(int i, int j, int n, int m, int[][] dp){
        if(i==n-1 && j==m-1){
            return dp[i][j] = 1;
        }

        if(dp[i][j] != -1){
            return dp[i][j];
        }

        int rightPaths = 0;
        int downPaths = 0;

        if(j+1 < m){
            rightPaths = up_rec(i,j+1,n,m);
        }

        if(i+1 < n){
            downPaths = up_rec(i+1,j,n,m);
        }

        int totalPaths = rightPaths + downPaths;
        return dp[i][j] = totalPaths;
    }

    public int up_tab(int i, int j, int n, int m, int[][] dp){
        for(int i=n-1; i>=0; i--){
            for(int j=m-1; j>=0; j--){
                if(i==n-1 && j==m-1){
                    dp[i][j] = 1;
                    continue;
                }

                int rightPaths = 0;
                int downPaths = 0;

                if(j+1 < m){
                    rightPaths = dp[i][j+1]; //up_rec(i,j+1,n,m);
                }

                if(i+1 < n){
                    downPaths = dp[i+1][j]; //up_rec(i+1,j,n,m);
                }

                int totalPaths = rightPaths + downPaths;
                dp[i][j] = totalPaths;
            }
        }

        return dp[0][0];
    }

    public int uniquePaths(int n, int m) {
        int[][] dp = new int[n][m];

        for(int[] d: dp){
            Arrays.fill(d,-1);
        }

        return up_memo(0,0,n,m, dp);
    }

    // fibonacci ================
    public static int fibonacci_rec(int n){
        if(n == 0 || n==1){
            return n;
        }

        int ans = fibonacci_rec(n-1) + fibonacci_rec(n-2);

        return ans;
    }

    public static int fibonacci_memoization(int n, int[] memo){
        if(n == 0 || n==1){
            // memo[n] = n;
            return memo[n] = n;
        }

        if(memo[n] != -1){
            return memo[n];
        }

        int ans = fibonacci_memoization(n-1, memo) + fibonacci_memoization(n-2, memo);

        return memo[n] = ans;
    }

    public static int fibonacci_tabulation(int N, int[] dp){
        for(int n=0; n<=N; n++){
            if(n == 0 || n==1){
                dp[n] = n;
                continue;
            }

            int ans = dp[n-1] + dp[n-2]; //fibonacci_memoization(n-1, memo) + fibonacci_memoization(n-2, memo);

            dp[n] = ans;
        }

        return memo[N];
    }

    public static void main(String[] args){
        int n = 5;


        // int nFibTerm = fibonacci_rec(n);
        int[] memo = new int[n+1];
        Arrays.fill(memo, -1);
        int nFibTerm = fibonacci_memoization(n, memo);


        System.out.println(nFibTerm);
    }
}