import java.util.Arrays;

import java.util.HashMap;

import java.util.List;

public class DynamicProgramming {

/*

* 1) When we have overlapping sub-problems, solving the same problems

* redundantly.

* 2) Optimal sub-structure: if we have the optimal solution of the sub

* problems,

* then we have the optimal solution of the main problem.

*

* There is one difference between memoization and dynamic programming. In

* memoization

* we solve the problem in the top down approach, that is whenever we need a

* value we

* calculate it and store it.

*

* In DP, we follow the bottom up approach, that is before having to want a

* value, we

* have all the necessary calculations done. We should avoid recursion here.

*/

public static void main(String args[]) {

DynamicProgramming dp = new DynamicProgramming();

System.out.println(dp.fibonacci(4));

System.out.println(dp.fibonacciMemo(4));

System.out.println(dp.fibonacciDP(4));

System.out.println(dp.stepsTo1(50));

System.out.println(dp.stepsTo1Memo(50));

System.out.println(dp.stepsTo1DP(50));

System.out.println(dp.staircase(10));

System.out.println(dp.staircaseMemo(10));

System.out.println(dp.staircaseDP(10));

System.out.println(dp.balancedBTs(5));

System.out.println(dp.balancedBTsMemo(5));

System.out.println(dp.balancedBTsDP(5));

System.out.println(dp.minCount(8));

System.out.println(dp.minCountMemo(8));

System.out.println(dp.sumPossible(10, Arrays.asList(3, 7, 6)));

System.out.println(dp.sumPossibleDP(10, Arrays.asList(3, 7, 6)));

System.out.println(dp.minChange(12, Arrays.asList(1, 2, 3, 5)));

System.out.println(dp.minChangeDP(12, Arrays.asList(1, 2, 3, 5)));

int[][] arr = new int[][] {

{ 3, 4, 1, 2 },

{ 2, 1, 8, 9 },

{ 4, 7, 8, 1 }

};

System.out.println(dp.minCostPath(arr));

System.out.println(dp.minCostPathDP(arr));

System.out.println(dp.lcs("asdfgh", "akdflgj"));

System.out.println(dp.lcsM("asdfgh", "akdflgj"));

System.out.println(dp.editDistance("adef", "gbde"));

System.out.println(dp.editDistance("adef", "gbde"));

System.out.println(dp.knapsack(new int[] { 6, 1, 2, 4, 5 }, new int[] { 10, 5, 4, 8, 6 }, 5, 0));

}

public int fibonacci(int n) {

// Basic Recursive approach.

if (n == 1 || n == 0) {

return n;

}

return fibonacci(n - 1) + fibonacci(n - 2);

}

public int fibonacciMemo(int n) {

// Following memoization - Calculating as we need.

int[] arr = new int[n + 1];

Arrays.fill(arr, -1);

return fibonacciMemo(n, arr);

}

public int fibonacciMemo(int n, int[] arr) {

if (n == 0 || n == 1) {

arr[n] = n;

return n;

}

if (arr[n] == -1) {

arr[n] = fibonacciMemo(n - 1, arr) + fibonacciMemo(n - 2, arr);

}

return arr[n];

}

public int fibonacciDP(int n) {

// Having all the values needed, before hand.

// All the work is done before.

int[] arr = new int[n + 1];

arr[0] = 0;

arr[1] = 1;

for (int i = 2; i < arr.length; i++) {

arr[i] = arr[i - 1] + arr[i - 2];

}

return arr[n];

}

public int stepsTo1(int n) {

/*

* We have to find the number of steps needed to reduce the n to 1.

* We have got three options to reduce:

* 1) subtract one from n

* 2) divide by 2

* 3) divide by 3

*

* The basic recursive approach.

*/

if (n == 1)

return 0;

int option1 = stepsTo1(n - 1);

int minimum = option1;

if (n % 3 == 0) {

int option2 = stepsTo1(n / 3);

if (option2 < minimum)

minimum = option2;

}

if (n % 2 == 0) {

int option3 = stepsTo1(n / 2);

if (option3 < minimum)

minimum = option3;

}

return minimum + 1;

}

public int stepsTo1Memo(int n) {

/*

* we are going to use memoization to associate every value

* from n to 2 with the minimum steps needed to reach 1.

*/

int[] arr = new int[n + 1];

Arrays.fill(arr, -1);

arr[0] = 0;

arr[1] = 0;

return stepsTo1Memo(n, arr);

}

private int stepsTo1Memo(int n, int[] arr) {

if (n == 1)

return arr[1];

if (arr[n] != -1)

return arr[n];

arr[n] = stepsTo1Memo(n - 1);

if (n % 3 == 0) {

int option2 = stepsTo1Memo(n / 3);

if (option2 < arr[n])

arr[n] = option2;

}

if (n % 2 == 0) {

int option3 = stepsTo1Memo(n / 2);

if (option3 < arr[n])

arr[n] = option3;

}

return arr[n] + 1;

}

public int stepsTo1DP(int n) {

// We are going to use DP

int[] arr = new int[n + 1];

arr[0] = 0;

arr[0] = 0;

return stepsTo1DP(n, arr);

}

private int stepsTo1DP(int n, int[] arr) {

for (int i = 2; i < arr.length; i++) {

int num = i;

int ans = num - 1;

ans = arr[ans] + 1;

num = i;

if (num % 3 == 0) {

int option2 = num / 3;

option2 = arr[option2] + 1;

if (ans > option2)

ans = option2;

}

num = i;

if (num % 2 == 0) {

int option3 = num / 2;

option3 = arr[option3] + 1;

if (ans > option3)

ans = option3;

}

arr[i] = ans;

}

return arr[n];

}

/*

* A child runs up a staircase with 'n' steps and can hop either 1 step,

* 2 steps or 3 steps at a time. Implement a method to count and return all

* possible ways in which the child can run up to the stairs.

*

* For example: 4

* (1, 3) , (3, 1) , (2, 2) , (1, 1, 1, 1), (1, 1, 2), (1, 2, 1), (2, 1, 1)

* Answer: 7

*/

public long staircase(int n) {

// Basic Recursion

if (n == 0) {

return 1;

}

Long value1 = staircase(n - 1);

if (n >= 2) {

Long value2 = staircase(n - 2);

value1 += value2;

}

if (n >= 3) {

Long value3 = staircase(n - 3);

value1 += value3;

}

return value1;

}

public long staircaseMemo(int n) {

// Use Memoization,to store the answers to prevent unnecessary computation

long[] arr = new long[n + 1];

arr[0] = 0;

return staircaseMemo(n, arr);

}

private long staircaseMemo(int n, long[] arr) {

if (n == 0) {

return 1;

}

if (arr[n] != 0) {

return arr[n];

}

long value1 = staircaseMemo(n - 1, arr);

if (n >= 2) {

long value2 = staircaseMemo(n - 2, arr);

value1 += value2;

}

if (n >= 3) {

long value3 = staircaseMemo(n - 3, arr);

value1 += value3;

}

arr[n] = value1;

return arr[n];

}

public long staircaseDP(int n) {

// Using Dynamic Programming now.

int[] arr = new int[n + 1];

arr[0] = 1;

return staircaseDP(n, arr);

}

private long staircaseDP(int n, int[] arr) {

for (int i = 1; i < arr.length; i++) {

int num = i;

int value = arr[num - 1];

if (i >= 2) {

num = i;

value += arr[num - 2];

}

if (i >= 3) {

num = i;

value += arr[num - 3];

}

arr[i] = value;

}

return arr[n];

}

/*

* Given height, how many structurally different balanced binary trees,

* can we construct. Where balanced means |left-height - right-height| <= 1.

* The first solution will be the recursive solution, the second one will

* use memoization and the third one will be the optimal solution using

* dynamic programming.

*

* The whole idea of the solution is, if we want the height of the tree to be h,

* then the sub trees will be atleast h-2 and atmost h-1, only then it will be

* balanced.

* That is, we will have three cases:

* 1) Height of left subtree = h-1 and height of right subtree = h-1

* 2) Height of left subtree = h-2 and height of right subtree = h-1

* 3) Height of left subtree = h-1 and height of right subtree = h-2

*

* Let x be height of left subtree and y be the height of right subtree

* So total will be x^2 + x*y + y*x

*/

public long balancedBTs(int height) {

if (height == 0 || height == 1) {

return 1;

}

long x = balancedBTs(height - 1);

long y = balancedBTs(height - 2);

return 2 * x * y + x * x;

}

public long balancedBTsMemo(int height) {

if (height == 0 || height == 1) {

return 1;

}

long[] arr = new long[height + 1];

arr[0] = arr[1] = 1;

return balancedBTsMemo(height, arr);

}

private long balancedBTsMemo(int height, long[] arr) {

if (arr[height] != 0)

return arr[height];

arr[height - 1] = balancedBTsMemo(height - 1, arr);

long x = arr[height - 1];

long y = arr[height - 2];

return 2 * x * y + x * x;

}

public long balancedBTsDP(int height) {

if (height == 0 || height == 1) {

return 1;

}

long[] arr = new long[height + 1];

arr[0] = arr[1] = 1;

return balancedBTsDP(height, arr);

}

private long balancedBTsDP(int height, long[] arr) {

for (int i = 2; i < arr.length; i++) {

long x = arr[i - 1];

long y = arr[i - 2];

arr[i] = x * x + 2 * x * y;

}

return arr[height];

}

/*

* Given an integer n, find and return the count of minimum numbers

* required to represent n as a sum of squares. That is, if n = 4, it

* can be represented by (1^2+1^2+1^2+1^2) and (2^2). The output will

* be 1, since 1 is the minimum count of number required to represent

* N as a sum of squares.

*/

// **** TOUGH ****

public int minCount(int n) {

if (n == 0)

return 0;

int minAns = Integer.MAX_VALUE;

for (int i = 1; i * i <= n; i++) {

int currAns = minCount(n - (i * i));

if (minAns > currAns) {

minAns = currAns;

}

}

return 1 + minAns;

}

public int minCountMemo(int n) {

int[] arr = new int[n + 1];

Arrays.fill(arr, -1);

return minCountMemo(n, arr);

}

private int minCountMemo(int n, int[] arr) {

if (n == 0)

return 0;

int minAns = Integer.MAX_VALUE;

for (int i = 1; i * i <= n; i++) {

int currAns;

if (arr[n - (i * i)] == -1) {

currAns = minCount(n - (i * i));

arr[n - (i * i)] = currAns;

} else {

currAns = arr[n - (i * i)];

}

if (minAns > currAns) {

minAns = currAns;

}

}

return 1 + minAns;

}

// We are given a target amount and a list of numbers.

// We have to find if any combination of the list of numbers

// can be added to result the amount. The same number can be used multiple

// times.

// Tough

public boolean sumPossible(int amount, List<Integer> numbers) {

if (amount == 0)

return true;

if (amount < 0)

return false;

for (Integer value : numbers) {

boolean val = sumPossible(amount - value, numbers);

if (val)

return val;

}

return false;

}

public boolean sumPossibleDP(int amount, List<Integer> numbers) {

return sumPossibleDP(amount, numbers, new HashMap<>());

}

private boolean sumPossibleDP(int amount, List<Integer> numbers, HashMap<Integer, Boolean> map) {

if (amount == 0)

return true;

if (amount < 0)

return false;

if (map.containsKey(amount))

return map.get(amount);

boolean answer = false;

for (Integer value : numbers) {

answer = sumPossibleDP(amount - value, numbers, map);

map.put(value, answer);

if (answer)

return answer;

}

return false;

}

// Minimum change: We are given an amount, and some coins

// We have to find the minimum number of coins that will make up that amount.

// For example: amount = 5 coins: 1,2,3: [{1,1,1,1,1}, {1,1,1,2}, {1,1,3},

// {2,2,1}, {2,3}

// The answer will be: {2,3}

// *****TOUGH***** :vv

public int minChange(int amount, List<Integer> coins) {

if (amount == 0)

return 0;

if (amount < 0)

return -1;

int minCoins = -1;

for (Integer coinVal : coins) {

int subCoins = minChange(amount - coinVal, coins);

if (subCoins != -1) {

subCoins++;

if (minCoins > subCoins || minCoins == -1) {

minCoins = subCoins;

}

}

}

return minCoins;

}

public int minChangeDP(int amount, List<Integer> coins) {

return minChangeDP(amount, coins, new HashMap<>());

}

private int minChangeDP(int amount, List<Integer> coins, HashMap<Integer, Integer> map) {

if (amount == 0)

return 0;

if (amount < 0)

return -1;

if (map.containsKey(amount))

return map.get(amount);

int minCoins = -1;

for (Integer coin : coins) {

int subCoins = minChangeDP(amount - coin, coins, map);

if (subCoins != -1) {

subCoins++;

if (subCoins < minCoins || minCoins == -1)

minCoins = subCoins;

map.put(amount, minCoins);

}

}

return minCoins;

}

/*

* Minimum Cost Path: An integer matrix of size (M x N) has been given.

* Find out the minimum cost to reach from the cell (0,0) to (M-1, N-1).

* Cost constitues the sum of values in the cells of the path taken.

* From a cell (i, j), you can move in three directions:

* 1. ((i+1), j) -> which is down

* 2. (i, (j+1)) -> which is right

* 3. ((i+1), (j+1))-> which is diagonal

*/

public int minCostPath(int[][] input) {

return minCostPath(input, 0, 0);

}

private int minCostPath(int[][] input, int i, int j) {

if (i == input.length - 1 && j == input[0].length - 1) {

// destination reached

return input[i][j];

}

if (i == input.length - 1 || j == input[0].length - 1)

return Integer.MAX_VALUE;

int rightAmount = minCostPath(input, i, j + 1);

int diagonalAmount = minCostPath(input, i + 1, j + 1);

int downAmount = minCostPath(input, i + 1, j);

return input[i][j] + Math.min(downAmount, Math.min(rightAmount, diagonalAmount));

}

public int minCostPathDP(int[][] input) {

int[][] storage = new int[input.length][input[0].length];

for (int[] arr : storage) {

Arrays.fill(arr, -1);

}

return minCostPathDP(input, storage, 0, 0);

}

private int minCostPathDP(int[][] input, int[][] storage, int i, int j) {

if (i == input.length - 1 && j == input[0].length - 1) {

// destination reached

storage[i][j] = input[i][j];

return storage[i][j];

}

if (i == input.length - 1 || j == input[0].length - 1)

return Integer.MAX_VALUE;

if (storage[i][j] != -1) {

return storage[i][j];

}

int rightAmount = minCostPathDP(input, storage, i, j + 1);

int diagonalAmount = minCostPathDP(input, storage, i + 1, j + 1);

int downAmount = minCostPathDP(input, storage, i + 1, j);

storage[i][j] = input[i][j] + Math.min(downAmount, Math.min(rightAmount, diagonalAmount));

return storage[i][j];

}

/*

* Longest Common Subsequence : LCS

* Given two strings, we have to find the longest common subsequence (not

* substring)

* To compute longest common subsequence, the brute force approach will be, to

* just have a list of subsequences from both the strings and then compare to

* find

* the longest common subsequence and return it's length.

*

* But the effective approach will be, to check if the first characters of the

* string are same or not. If they are same - Then we can increment the answer.

* If not, then either we can ignore the first character of either of the

* strings

* and compare it or simply ignore the first characters of both the strings.

*

* But we can skip writing the case wherein, we skip the first characters of

* both

* the strings because somewhere down the line, it will get covered.

*/

public int lcs(String one, String two) {

if (one.length() == 0 || two.length() == 0)

return 0;

if (one.charAt(0) == two.charAt(0)) {

return 1 + lcs(one.substring(1), two.substring(1));

} else {

int option1 = lcs(one, two.substring(1));

int option2 = lcs(one.substring(1), two);

return Math.max(option1, option2);

}

}

/*

* To use Dynamic Programming here first we have to know the storage space

* required for this problem. If we are given two strings, what can be the

* number of unique combinations for which we have to save the result.

* In this case, if we have two strings of length n and m -> Then the total

* unique combinations will be (n+1)(m+1).

*/

public int lcsM(String one, String two) {

int[][] storage = new int[one.length() + 1][two.length() + 1];

for (int[] arr : storage) {

Arrays.fill(arr, -1);

}

return lcsM(one, two, storage);

}

private int lcsM(String one, String two, int[][] storage) {

// THis is done using Memoization.

if (one.length() == 0 || two.length() == 0) {

return 0;

}

int m = one.length();

int n = two.length();

if (storage[m][n] != -1) {

return storage[m][n];

}

if (one.charAt(0) == two.charAt(0)) {

storage[m][n] = 1 + lcsM(one.substring(1), two.substring(1), storage);

} else {

int option1 = lcsM(one, two.substring(1), storage);

int option2 = lcsM(one.substring(1), two, storage);

storage[m][n] = Math.max(option1, option2);

}

return storage[m][n];

}

/*

* Edit Distance: Minimum number of oprations to make one string equal to other.

* These operations will be Insert, Delete, Substitute/Replace, No swapping in

* the same string

*

* The base case will be: If we have an empty string, then we will return the

* length of the

* other string. That is if one is empty - we will return two's length and vice

* versa

* Why? Because that will be the number of operations required to convert one

* into two.

* one is empty - we will have to delete all the elements of two, so number of

* operations is two's length

* two is empty - we will have to insert all the elements of one into two, that

* will make the number of

* insertions as one's length.

*

* One thing has to understood, we are not modifying any of the string, since we

* just

* have to give the number of modifications. If we plan on inserting- Do not

* insert just

* add the count, If we plan on deleting - increase the count, substitution -

* similar thing

*/

public int editDistance(String one, String two) {

if (one.length() == 0)

return two.length();

if (two.length() == 0)

return one.length();

if (one.charAt(0) == two.charAt(0)) {

return editDistance(one.substring(1), two.substring(1));

} else {

// Insertion

// We have inserted a char in two.

int option1 = editDistance(one, two.substring(1));

// Deletion

// We have deleted first char from one

int option2 = editDistance(one.substring(1), two);

// Substitution

int option3 = editDistance(one.substring(1), two.substring(1));

return 1 + Math.min(option1, Math.min(option2, option3));

}

}

public int editDistanceM(String one, String two) {

int[][] storage = new int[one.length()][two.length()];

for (int[] arr : storage) {

Arrays.fill(arr, -1);

}

return editDistanceM(one, two, storage);

}

private int editDistanceM(String one, String two, int[][] storage) {

// This is done using Memoization

int m = one.length();

int n = two.length();

if (m == 0) {

storage[m][n] = n;

return storage[m][n];

}

if (n == 0) {

storage[m][n] = m;

return storage[m][n];

}

if (one.charAt(0) == two.charAt(0)) {

storage[m][n] = editDistanceM(one.substring(1), two.substring(1), storage);

} else {

int option1 = editDistanceM(one, two.substring(1), storage);

int option2 = editDistanceM(one.substring(1), two, storage);

int option3 = editDistanceM(one.substring(1), two.substring(1), storage);

storage[m][n] = 1 + Math.min(option1, Math.min(option2, option3));

}

return storage[m][n];

}

/*

* 0 1 Knapsack

* Suppose a theif goes to rob a store, now there is a limit on the weight he

* can carry

* In that limit he has to choose the items which will yeild the highest value.

* Suppose there are 5 items with following weights and respective values and

* weight limit is 5kg

* W: 6, 1, 2, 4, 5

* V: 10, 5, 4, 8, 6

* There can be three cases:

* (1,2) -> 5+4 = 9

* (1,4) -> 5+8 = 13

* (5) -> 6

*/

public int knapsack(int[] weights, int[] values, int maxWeight, int i) {

if (i == weights.length || maxWeight == 0)

return 0;

if (weights[i] > maxWeight) {

return knapsack(weights, values, maxWeight, i + 1);

} else {

int withWeight = values[i] + knapsack(weights, values, maxWeight - weights[i], i + 1);

int withoutWeight = knapsack(weights, values, maxWeight, i + 1);

return Math.max(withWeight, withoutWeight);

}

}

//Now, how can we memoize the knapsack problem?

//There is a serious possibility of overlapping sub problems which can be mapped

//to a particular weight and the value of the particular index that we are on.

//So we will memoize based, upon the the particular maximum weight and index.

}