Climb Stairs, Leet Code 70

 I/P: 8

O/P:

34

34

1 1 2 3 5 8 13 21 34

34

1 1 2 3 5 8 13 21 34

Recursion + Memoization

Tabulation

import java.util.Arrays;
import java.util.Scanner;

public class Climb_Stairs_dp {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        System.out.println(countPaths(n));

        int[] dp = new int[n + 1];
        Arrays.fill(dp, -1);
        System.out.println(countPathsMemoization(n, dp));
        display(dp);

        Arrays.fill(dp, -1);
        System.out.println(countPathsTabulation(n, dp));
        display(dp);
    }

    private static int countPaths(int n) {
        if (n == 0)
            return 1;
        else if (n < 0)
            return 0;

        return countPaths(n - 1) + countPaths(n - 2);
    }

    private static int countPathsMemoization(int n, int[] dp) {
        if (n == 0)
            return dp[n] = 1;
        else if (n < 0)
            return 0;
        if (dp[n] != -1) return dp[n];

        return dp[n] = countPathsMemoization(n - 1, dp) + countPathsMemoization(n - 2, dp);
    }

    private static int countPathsTabulation(int N, int[] dp) {
        for (int n = 0; n <= N; n++) {
            if (n <= 1) {
                dp[n] = 1;
                continue;
            }
            //if (dp[n] != -1) return dp[n];
            dp[n] = dp[n - 1] + dp[n - 2];
            //return dp[n] = countPathsMemoization(n - 1, dp) + countPathsMemoization(n - 2, dp);
        }

        return dp[N];
    }

    public static void display(int[] dp) {
        for (int i : dp) {
            System.out.print(i + "\t");
        }
        System.out.println();
    }
}