ClimbStairs.java

package com.learning.leet.problems;

import java.util.HashMap;
import java.util.Map;

/**
 * Created by sargonbenjamin on 7/8/19.
 * https://leetcode.com/problems/climbing-stairs/
 */
public class ClimbStairs {


    public static void main(String args[]){
        ClimbStairs climbStairs = new ClimbStairs();
        //int val = climbStairs.climbStairs(5, new int[]{1,2,3});
        int val = climbStairs.climbStairs(5, new int[]{6});
        System.out.println("Value is " + val);
    }

    /**
     * customizeable jumps
     * @param n
     * @param jumps
     * @return
     */
    public int climbStairs(int n, int jumps[]) {
        Map<Integer,Integer> cache = new HashMap<>();

        return climbStairsHelper(n,jumps,cache);
    }

    public int climbStairsHelper(int n, int jumps[], Map<Integer,Integer> cache) {
        if(n<0)return 0;
        if(n==0 || n==1)return 1;

        if(cache.containsKey(n))return cache.get(n);

        int total = 0;
        for(int jump : jumps){
            total+=climbStairsHelper(n-jump, jumps, cache);
        }


        cache.put(n,total);
        return cache.get(n);
    }

    /**
     * jumps of 1 or 2
     * @param n
     * @return
     */
    public int climbStairsIteratively(int n){
        int a = 1;
        int b = 2;
        int i = 3;
        int curr = 0;
        if(n<3)return n;

        while(i++<=n){
            curr = a+b; //3
            int temp = b; //2
            b = curr; //3
            a = temp; //2
        }

        return curr;
    }

    /**
     * customizeable jumps
     * @param n
     * @param jumps
     * @return
     */
    public int climbStairsIteratively(int n, int jumps[]){
        int[] arr = new int[n+1];
        arr[0] = 1;
        arr[1] = 1;

        for(int i = 0 ; i<arr.length; i++){
            int total = 0;
            for(int jump : jumps){
                if(i-jump>=0){
                    total += arr[i-jump];
                }
            }
            if(i>1)arr[i]=total;
        }
        return arr[n];

    }



}