Java Dynamic Programming

1) This class handles the Fibonacci Series Problem using Dynamic Programming, and Memoization

	/**
	*
	*/
	package com.alogorithms.dynamicprogramming;
	import java.util.ArrayList;
	import java.util.HashMap;
	import java.util.Map;
	/**
	* @author Kiran Kanaparthi
	*
	*/
	public class FibonacciNumberDynamic {
	//0 1 1
	/**
	*
	* @param n
	*/
	private void printFibonacciIterative(int n) {
	int a =0, b=0;
	int c = 1;
	//a = 0;
	b = 1;
	System.out.print(" " +a+ " "+b);
	for(int i=2;i<10;i++) {
	int temp = c;
	c= c+b;
	b = temp;
	System.out.print(" "+c);
	}
	}
	private void fiboIterative(int n) {
	int a=0,b=1;
	System.out.print(" "+a+" "+b);
	for(int i=2;i<n;i++) {
	int c = a+b;
	a = b;
	b = c;
	System.out.print(" "+c);
	}
	}
	/**
	*
	* @param n
	*/
	private int printFibonacciRecursive(int n) {
	if(n==0 || n==1) {
	return n;
	} else {
	return printFibonacciRecursive(n-1)+printFibonacciRecursive(n-2);
	}
	}
	public int fibonacciRecursive(int n) {
	if(n <= 1) {
	return n;
	}
	return fibonacciRecursive(n-1) + fibonacciRecursive(n-2);
	}
	/**
	*
	* @param n
	* @param computedValues
	* @return
	*/
	private int printFiboRecursionDynamic(int n,
	Map<Integer,Integer> computedValues) {
	if(computedValues!=null) {
	if(computedValues.containsKey(n)) {
	return computedValues.get(n);
	}
	}
	if(n==0) {
	return 0;
	}
	if(n==1) {
	return 1;
	}
	int fibo = printFiboRecursionDynamic(n-1,computedValues)+
	printFiboRecursionDynamic(n-2,computedValues);
	if(computedValues!=null) {
	computedValues.put(n, fibo);
	}
	return fibo;
	}
	/**
	*
	* @param n
	* @param computedValues
	* @return
	*/
	private int printFiboRecursion(int n) {
	if(n==0) {
	return 0;
	}
	if(n==1) {
	return 1;
	}
	int fibo = printFiboRecursion(n-1)+ printFiboRecursion(n-2);
	return fibo;
	}
	/**
	* @param args
	*/
	public static void main(String[] args) {
	FibonacciNumberDynamic fibonacciNumberDynamic = new FibonacciNumberDynamic();
	System.out.println(" Started Fibonacci Iterative Method ");
	int n = 50;
	fibonacciNumberDynamic.fiboIterative(10);
	System.out.println("\n Printed Fibo numbers ");
	fibonacciNumberDynamic.printFibonacciIterative(n);
	long startTime = System.currentTimeMillis();
	System.out.println("\n Started Fibonacci Recursive Method ");
	Map<Integer,Integer> mapValues = new HashMap<>();
	for(int i=0;i<n;i++) {
	System.out.print(" "+fibonacciNumberDynamic.printFiboRecursion(i));
	}
	long endTime = System.currentTimeMillis();
	System.out.println("\n\n Total time taken for the process to complete is "
	+ ((endTime-startTime))+" milli seconds ");
	long startTimeDynamic = System.currentTimeMillis();
	for(int i=0;i<n;i++) {
	System.out.print(" "+fibonacciNumberDynamic.
	printFiboRecursionDynamic(i,mapValues));
	}
	ArrayList al = new ArrayList<>();
	long endTimeDynamic = System.currentTimeMillis();
	System.out.println("\n\n Total time taken for the process "
	+ " using Dynamic Programming -> to complete is "
	+ ((endTimeDynamic-startTimeDynamic))+" milli seconds ");
	}
	}

view raw FibonacciNumberDynamic.java hosted with ❤ by GitHub

2) This class solves the Stair Case Problem by finding the Number of Jumps possible to the Top of the StairCase.

	/**
	*
	*/
	package com.alogorithms.dynamicprogramming;
	/**
	* @author Kiran Kanaparthi
	*
	* This class gets all the possible Solutions that
	* are possible for a given StairCase, when a Child can
	* Jump either 1 step, or 2 steps, or 3 steps up to the
	* nth Stair.
	* As The possibilities are either one of these at a time,
	* not one after the other, We simply add all the possibilities
	*
	* Using The Memoization technique the Previous results are cached
	* and reused.
	*
	*
	*/
	public class StairCaseForJumps {
	/**
	*
	* @param n
	* @param cache
	* @return
	*/
	private int getAllJumpsForStaircaseMemoization(int n, int[] cache) {
	if(n<0) {
	return 0;
	} else if(n==0) {
	return 1;
	} else if(cache[n]!=0) {
	return cache[n];
	} else {
	cache[n] = getAllJumpsForStaircaseMemoization(n-1, cache)+
	getAllJumpsForStaircaseMemoization(n-2, cache)+
	getAllJumpsForStaircaseMemoization(n-3, cache);
	}
	return cache[n];
	}
	/**
	*
	* @param n
	* @return
	*/
	private int getAllJumpsForStairCaseRecursive(int n) {
	if(n<0) {
	return 0;
	} else if(n==0) {
	return 1;
	}
	return getAllJumpsForStairCaseRecursive(n-1)+
	getAllJumpsForStairCaseRecursive(n-2)+
	getAllJumpsForStairCaseRecursive(n-3);
	}
	/**
	* @param args
	*/
	public static void main(String[] args) {
	StairCaseForJumps stairCaseForJumps =
	new StairCaseForJumps();
	int totalJumpsPossible = stairCaseForJumps.
	getAllJumpsForStairCaseRecursive(7);
	System.out.println(" Total Jumps Possible "+totalJumpsPossible);
	int totalJumpsForMemoizaton =
	stairCaseForJumps.getAllJumpsForStaircaseMemoization(7, new int[101]);
	System.out.println(" totalJumpsForMemoizaton "+totalJumpsForMemoizaton);
	}
	}

view raw StairCaseForJumps.java hosted with ❤ by GitHub

3) This class Solves the Coin Change problem using Dynamic Programming and Memoization

	/**
	*
	*/
	package com.alogorithms.dynamicprogramming;
	import java.util.Map;
	import java.util.concurrent.ConcurrentHashMap;
	/**
	* @author Kiran Kanaparthi
	*
	* This class Solves the Coin Change Problem
	* to find the number of Ways the change can be
	* made for the given Total, using the Coins.
	*
	*/
	public class CoinChangeProblem {
	/**
	*
	* @param amount
	* @param denominations
	* @param index
	* @return
	*/
	private long makeChange(int amount,int[] denominations,
	int index,Map<String,Long> cacheMap) {
	System.out.println(" index at each step "+ index);
	if(amount==0) { return 1;}
	if(index>=denominations.length) { return 0;}
	String preComputedKey = amount+"_"+index;
	if(cacheMap.containsKey(preComputedKey)) {
	return cacheMap.get(preComputedKey);
	}
	int denominationAmount = denominations[index];
	System.out.println(" index "+index
	+" denominationAmount "+denominationAmount);
	Long waysToMakeChange = 0l;
	for(int i=0;i*denominationAmount<=amount;i++) {
	int amountRemaining = amount - i*denominationAmount;
	System.out.println(" amountRemaining "+amountRemaining
	+" denominations "+denominations[index]
	+" index "+index );
	waysToMakeChange += makeChange
	(amountRemaining, denominations, index+1,cacheMap);
	System.out.println("waysToMakeChange "+waysToMakeChange);
	}
	cacheMap.put(preComputedKey, waysToMakeChange);
	return waysToMakeChange;
	}
	/**
	* @param args
	*/
	public static void main(String[] args) {
	CoinChangeProblem coinChangeProblem =
	new CoinChangeProblem();
	int n = 250;
	int[] denominations = new int[] {41,34,46,9,37,32,42,21,7,13,1,24,3,43,2,23,8,45,19,30,29,18,35,11};
	int index = 0;
	Map<String,Long> cacheMap = new ConcurrentHashMap<>();
	long waysToMakeChange =
	coinChangeProblem.makeChange(n, denominations, index,cacheMap);
	System.out.println(" The Number of Ways "
	+ " to Make change are "+waysToMakeChange);
	}
	}

view raw CoinChange.java hosted with ❤ by GitHub