Can take one or two steps to get to the top of the staircase write function num_ways(N)

daily-code-001.java

import java.util.ArrayList; 

class Staircase {
    /**
    *  Can take one or two steps to get to the top of the staircase
    *  write function num_ways(N)
    */ 
    public static int num_ways(int n){
        if (n==0 || n==1)
            return 1;
        return num_ways(n-1) + num_ways(n-2);
    }

    public static int num_ways_bottom_up(int n){
        if (n==0||n==1)
            return 1;
        int[] nums = new int[n+1];
        nums[0] = 1;
        nums[1] = 1;
        for (int i=2; i<=n; i++){
            nums[i] = nums[i-1] + nums[i-2];
        }
        return nums[n];
    }

    /**
    *  Variation:
    *  Given a set of steps allowed 
    *  num_ways(N,X) where X = {1,3,5}
    */
    public static int num_ways(int n, int[] X){
        if (n==0)
            return 1;
        int total = 0;
        for (int i: X)
            if (n-i >= 0)
                total += num_ways(n-i);
        return total;
    }

    /**
     * Needs to be debugged!
     */
    public static int num_ways_bottom_up(int n, int[] X){
        if (n==0)
            return 1;
        int[] nums = new int[n+1];
        nums[0] = 1;
        for (int i=1; i<=n; i++){
            int total = 0;
            for (int j: X){
                if (i-j >= 0)
                    total += nums[i -j];
            }
            nums[i] = total; 
        }   
        return nums[n];
    }

    public static void main(String [] args){
        int[] example = {1,2,3};
        int steps = 4;
        System.out.println(num_ways(steps));
        System.out.println(num_ways_bottom_up(steps));
        System.out.println(num_ways(steps, example));
        System.out.println(num_ways_bottom_up(steps, example));
    }
}