dymanic problems

COIN Changing 

     coins 1 2 3                        total 5   
        
 1 1 1 1      1 one way to get 5
 1 1 1 2       2 way to get 5
 1 1 3
 2 3
 1 2 2
                                                j

i/j	0	1	2	3	4	5
1	1	1	1	1	1	1
2	1	1	2	2	3	3
3	1	1	2	3	4	5

             

if j>= coins[i]
T[i][j] =  T[i-1][j] + T[i][j-coins[i]];
else
 T[i][j] =  T[i-1][j] ;

public int numberOfSolutions(int total, int coins[]){
int temp[][] = new int[coins.length+1][total+1];
for(int i=0; i <= coins.length; i++){
temp[i][0] = 1;
}
for(int i=1; i <= coins.length; i++){
for(int j=1; j <= total ; j++){
if(coins[i-1] > j){
temp[i][j] = temp[i-1][j];
}
else{
temp[i][j] = temp[i][j-coins[i-1]] + temp[i-1][j];
}
}
}
return temp[coins.length][total];
} Longest Increasing Subsequence J I 3  4 -1 0  6 2 3 1 2 1 2 3 3 4 If arr[j]<arr[i] T[i]=max(T[i],T[j]+1) https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/LongestIncreasingSubsequence.java Longest Common Subsequence i/j a b c d a f 0 0 0 0 0 0 0 a 0 1 1 1 1 1 1 c 0 1 1 2 2 2 2 b 0 1 2 2 2 2 2 c 0 1 2 3 3 3 3 f 0 1 2 3 3 3 4 if(str[i]==str[j]) T[i][j]=T[i-1][j-1]+1; else T[i][j]=max(T[i][j-1]+T[i-1][j])+1; https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/LongestCommonSubsequence.java Longest Path in a matrix class GFG {  public static int n = 3;  // Function that returns length of the longest path  // beginning with mat[i][j]  // This function mainly uses lookup table dp[n][n]  static int findLongestFromACell(int i, int j, int mat[][], int dp[][])  {  // Base case  if (i < 0 || i >= n || j < 0 || j >= n)  return 0;  // If this subproblem is already solved  if (dp[i][j] != -1)  return dp[i][j];  // To store the path lengths in all the four directions  int x = Integer.MIN_VALUE, y = Integer.MIN_VALUE, z = Integer.MIN_VALUE, w = Integer.MIN_VALUE;  // Since all numbers are unique and in range from 1 to n*n,  // there is atmost one possible direction from any cell  if (j < n - 1 && ((mat[i][j] + 1) == mat[i][j + 1]))  x = dp[i][j] = 1 + findLongestFromACell(i, j + 1, mat, dp);  if (j > 0 && (mat[i][j] + 1 == mat[i][j - 1]))  y = dp[i][j] = 1 + findLongestFromACell(i, j - 1, mat, dp);  if (i > 0 && (mat[i][j] + 1 == mat[i - 1][j]))  z = dp[i][j] = 1 + findLongestFromACell(i - 1, j, mat, dp);  if (i < n - 1 && (mat[i][j] + 1 == mat[i + 1][j]))  w = dp[i][j] = 1 + findLongestFromACell(i + 1, j, mat, dp);  // If none of the adjacent fours is one greater we will take 1  // otherwise we will pick maximum from all the four directions  return dp[i][j] = Math.max(x, Math.max(y, Math.max(z, Math.max(w, 1))));  }  // Function that returns length of the longest path  // beginning with any cell  static int finLongestOverAll(int mat[][])  {  // Initialize result  int result = 1;  // Create a lookup table and fill all entries in it -1 int[][] dp = new int[n][n];  for (int i = 0; i < n; i++)  for (int j = 0; j < n; j++)  dp[i][j] = -1;  // Compute longest path beginning from all cells  for (int i = 0; i < n; i++) {  for (int j = 0; j < n; j++) {  if (dp[i][j] == -1)  findLongestFromACell(i, j, mat, dp);  // Update result if needed  result = Math.max(result, dp[i][j]);  }  }  return result;  }  // driver program  public static void main(String[] args)  {  int mat[][] = { { 1, 2, 9 },  { 5, 3, 8 },  { 4, 6, 7 } };  System.out.println("Length of the longest path is " + finLongestOverAll(mat));  }  } Subset sum Problem

   CHECK 11 SUM PRESENT IN AN ARRAY [2,3,7,8,10]
   (if element of last row & last column is TRUE then sum exists)

               

0

1

2

3

4

5

6

7

8

9

10

11

2

T

F

T

F

F

F

F

F

F

F

F

F

3

T

F

T

T

F

T

F

F

F

F

F

F

7

T

F

T

T

F

T

F

T

F

T

T

F

8

T

F

T

T

F

T

F

T

T

T

T

T

10

T

F

T

T

F

T

F

T

T

T

T

T

   Answer (8,3)

if j>= input[i]
T[i][j] =  T[i-1][j] ;
else
 T[i][j] = T[i-1][j] T[i-1][j-input[i]] ;

	* Space complexity - O(input.size*total_sum)
	*
	* Time complexity - O(input.size * total_sum)
	public class SubsetSum {
	public boolean subsetSum(int input[], int total) {
	boolean T[][] = new boolean[input.length + 1][total + 1];
	for (int i = 0; i <= input.length; i++) {
	T[i][0] = true;
	}
	for (int i = 1; i <= input.length; i++) {
	for (int j = 1; j <= total; j++) {
	if (j - input[i - 1] >= 0) { (go input[i] steps back)
	T[i][j] = T[i - 1][j] || T[i - 1][j - input[i - 1]];
	} else {
	T[i][j] = T[i-1][j]; (copy from up row)
	}
	}
	}
	return T[input.length][total];
	}
	public boolean partition(int arr[]) {
	int sum = 0;
	for (int i = 0; i < arr.length; i++) {
	sum += arr[i];
	}
	if (sum % 2 != 0) {
	return false;
	}
	sum = sum / 2;
	boolean[][] T = new boolean[arr.length + 1][sum + 1];
	for (int i = 0; i <= arr.length; i++) {
	T[i][0] = true;
	}
	for (int i = 1; i <= arr.length; i++) {
	for (int j = 1; j <= sum; j++) {
	if (j - arr[i - 1] >= 0) {
	T[i][j] = T[i - 1][j - arr[i - 1]] || T[i - 1][j];
	} else {
	T[i][j] = T[i-1][j];
	}
	}
	}
	return T[arr.length][sum];
	}
	public static void main(String args[]) {
	SubsetSum ss = new SubsetSum();
	int arr[] = {1, 3, 5, 5, 2, 1, 1, 6};
	System.out.println(ss.partition(arr));
	int arr1[] = {2, 3, 7, 8};
	System.out.print(ss.subsetSum(arr1, 11));
	}
	}

---

MINIMUM EDIT DISTANCE :

		a	b	c	d	e	F
	0	1	2	3	4	5	6
a	1	0	1	2	3	4	5
z	2	1	1	2	3	4	5
c	3	2	2	1	2	3	4
e	4	3	3	2	2	2	3
d	5	4	4	3	2	3	3

Operations :

F->d

d (delete)

b->z

Formula :

if(str1[i]==str[j])

T[I][J]==T[i-1][j-1]

else

T[I][J]==min(T[i-1][j],T[i-1][j-1],T[i][j-1])+1

 https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/EditDistance.java

---

Cutting Rod to maximize profit

 

rod	1	2	3	4
price	2	5	7	8

i/j		0	1	2	3	4	5
2	1	0	2	4	6	8	10
5	2	0	2	5	7	10	12
7	3	0	2	5	7	10	12
8	4	0	2	5	7	10	12

Answer 1,2,2

Formula:

if(j>=i)

T[i][j]=max(T[i-1][j]+T[i-1][j-i])

else

T[ii][j]=T[i-1][j]

---

PICK FROM EITHER SIDE TO MAXIMIZE VALUE

                                               3             9             1            2

	1	2	3	4
1	f,s (3,0)	(9,3)	(4,9)	(11,4)
2		(9,0)	(9,1)	(10,2)
3			(1,0)	(2,1)
4				(2,0)

1	2	3	4
3	9	1	2

 T[i][j]=max(T[i+1][j] second+ val[i]), T[i][j-1] second+ val[j])

 T[i][j].second=max(T[i+1][j] first or val[i]), T[i][j-1] first)

 https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/NPotGold.java

---

Cutting Rod to maximize profit

 

rod	1	2	3	4
price	2	5	7	8

i/j		0	1	2	3	4	5
2	1	0	2	4	6	8	10
5	2	0	2	5	7	10	12
7	3	0	2	5	7	10	12
8	4	0	2	5	7	10	12

Answer 1,2,2

Formula:

if(j>=i)

T[i][j]=max(T[i-1][j]+T[i-1][j-i])

else

T[ii][j]=T[i-1][j]

---

Word Break Problem :

GIVEN A STRING & DICTIONARY YOU HAVE TO TELL WHETHER EACH WORDS IN A STRING BELONGS TO DICTIONARY

(IAMC SHOULD RETURN FALSE)

I	a	m	a	c	e
0	1	2	3	4	5

i/j	0	1	2	3	4	5
0	T	T	T(0)	T(1)	F	T(0)
1		T	T	T(2)	F	T(2)
2			F	F	F	F
3				T	F	T(3-5)
4					F	F
5						F

Answer I, AM, ACE

Formula:

if(INPUT[I--J] IS IN DICTIONARY

T[i][j]=TRUE

else

T[i][j]=TRUE IF(T[I][K] && T[K+1][J])==TRUE

---

EGG DROPPING PROBLEM

GIVEN CERTAIN NUMBER OF FLOORS & EGGS find from which floor egg will break

egg/floors	1	2	3	4	5	6
1	1	2	3	4	5	6
2	1	2	2	3	3	3

floors 1 2 3 4 5 6 min(1+max(if it breaks,if it doesnt break)) 1 + max(0,3)= 4 (floor 1) 1 + max(1,3)= 4  (floor 2) 1 + max(2,2)= 3   (floor 3) 1 + max(3,2)= 4    (floor 4) 1 + max(4,1)= 5    (floor 5) 1 + max(5,0)= 6   (floor 5)

T[i][j]= T[i-1][j]

else

T[i][j]=1+min(max(T[i-1][k-1],T[i][j-k])

where k is 1...j

---

Matrix Chain Multiplication

GIVEN CERTAIN NUMBER what order should multiply them such as multiplication is minimum remember

0	1	2	3
[2,3]	[3,6]	[6,4]	[4,5]

l=3 72+(2*3*4) = 96 36+(2*6*4) = 84 l=4 132+(2*3*5)=162 36+120+2*6*5=260 84+(2*4*5)=124 0 1 2 3 0 0 36 (0,1)(2,2) 84 (0,3)(4,4) 124 1 0 72 (1,2)(3,3) 132 2 0   120

T[i][j]= T[i-1][j]

else

T[i][j]=1+min(max(T[i-1][k-1],T[i][j-k])

where k is 1...j

---