Category: Dynamic Programming

Snake and ladders game

admin / / Algorithms, Dynamic Programming

© Parineeth M R

Question 57. Find the least number of dice throws needed to complete the snake and ladders game

To find the least number of dice throws, we use the following dynamic programming technique:

1. Initialize the least number of throws needed to reach the positions 1-6 on the board as 1 since we can reach these positions with a single dice throw of a 6-sided dice

2. For any remaining position, we can either reach it from
• any of the previous 6 positions with one dice throw. If there is a snake at a previous position, then we ignore that cell while calculating the least number of throws for the current position

• or we can reach it by a ladder if present from some previous position. If there is a ladder from position I to position P, and we need N throws to reach I, then we can reach P also in N throws.

So we use the formula below to calculate the least number of throws for positions greater than 6

3. The least number of throws to reach the final position of the board gives the least number of throws needed to complete the game

C/C++


/*is_snake: if there is a snake at position 20, then is_snake[20] is set to 1
ladder: if there is a ladder from position 30 to 44, then ladder[44] = 30.
	if there is no ladder at location 90 then ladder[90] = -1
predecessor: this array has the previous board position from where we came to 
	current position with least number of dice throws. If predecessor[100]   
	= 95, then we reached 100 from 95. It is computed and returned. 
Return value: least number of throws to reach the final position on the board
*/
int find_least_throws(int is_snake[], int ladder[], int predecessor[]) 
{
	/*for a particular position pos on the board, least_throws[pos] will store
	the least number of dice throws required to reach the position*/
	int least_throws[MAX_POSITIONS_ON_BOARD + 1];
	int min_throws, i;
	int pos, prev_pos, ladder_start_pos;

	/*Positions from 1 to 6 can be reached from a single dice throw*/
	for (pos = 1; pos <= 6; pos++) {
		least_throws[pos] = 1;
		predecessor[pos] = 0;
	}

	for (pos = 7; pos <= MAX_POSITIONS_ON_BOARD; ++pos) {
		min_throws = MAX_POSITIONS_ON_BOARD;

		/*Find how many dice throws are needed to reach pos from any of 
		the 6 previous cells*/
		for (i = 1; i <= 6; ++i) {
			prev_pos = pos - i;

			if (is_snake[prev_pos])
				continue;

			/*Pick the minimum throws needed from the 6 previous cells*/
			if (least_throws[prev_pos] + 1 < min_throws) {
				min_throws = least_throws[prev_pos] + 1;
				predecessor[pos] = prev_pos;
			}
		}

		/*Suppose we are at pos = 14 and ladder[14] = 4, then there is a ladder
		from 4 to 14. So number of dice throws needed to reach 14 = number of 
		dice throws needed to reach position 4*/
		ladder_start_pos = ladder[pos];
		if (ladder_start_pos != -1) {
			if (least_throws[ladder_start_pos] < min_throws) {
				min_throws = least_throws[ladder_start_pos];
				predecessor[pos] = ladder_start_pos;
			}
		}

		least_throws[pos] = min_throws;
	}
	return least_throws[MAX_POSITIONS_ON_BOARD];
}

Java


/*isSnake: if there is a snake at position 20, isSnake[20] is true
ladder: if there is a ladder from position 30 to 44, then ladder[44] = 30.
	if there is no ladder at location 90 then ladder[90] = -1
predecessor: this array has the previous board position from where we came to 
	current position with least number of dice throws. If predecessor[100]   
	= 95, then we reached 100 from 95. It is computed and returned. 
Return value: least number of throws to reach the final position on the board
*/
public static int findLeastThrows(boolean[] isSnake, int[] ladder, 
					int[] predecessor) {
	/*for a particular position pos on board, leastThrows[pos] will store
	the least number of dice throws required to reach the position*/
	int[] leastThrows = new int [MAX_POSITIONS_ON_BOARD + 1];

	/*All positions from 1 to 6 can be reached from a single dice throw*/
	int pos;
	for (pos = 1; pos <= 6; pos++) {
		leastThrows[pos] = 1;
		predecessor[pos] = 0;
	}

	for (pos = 7; pos <= MAX_POSITIONS_ON_BOARD; ++pos) {
		int minThrows = MAX_POSITIONS_ON_BOARD;

		/*Find how many dice throws are needed to reach pos from any of
		the 6 previous cells*/
		for (int i = 1; i <= 6; ++i) {
			int prevPos = pos - i;

			if (isSnake[prevPos])
				continue;

			/*Pick minimum throws needed from the 6 previous cells*/
			if (leastThrows[prevPos] + 1 < minThrows) {
				minThrows = leastThrows[prevPos] + 1;
				predecessor[pos] = prevPos;
			}
		}

		/*Suppose we are at pos = 14 and ladder[14] = 4, then there is 
		a ladder from 4 to 14. So number of dice throws needed to reach 
		14 = number of dice throws needed to reach position 4*/
		int ladderStartPos = ladder[pos];
		if (ladderStartPos != -1) {
			if (leastThrows[ladderStartPos] < minThrows) {
				minThrows = leastThrows[ladderStartPos];
				predecessor[pos] = ladderStartPos;
			}
		}

		leastThrows[pos] = minThrows;
	}
	return leastThrows[MAX_POSITIONS_ON_BOARD];
}

Python


#is_snake: if there is a snake at position 20, is_snake[20] is set to True
#ladder:  if there is a ladder from position 30 to 44, then ladder[44] = 30.
#	if there is no ladder at location 90 then ladder[90] = -1
#Return value:  1. least number of throws to reach the position on the board
#		2. predecessor list
def find_least_throws(is_snake, ladder) :

	#for a particular position pos on the board, least_throws[pos] will store
	#the least number of dice throws required to reach the position
	least_throws = [0] * (MAX_POSITIONS_ON_BOARD + 1)

	#predecessor list has the previous board position from where we came to 
	#current position with least number of dice throws. If predecessor[100]   
	# = 95, then we reached 100 from 95.
	predecessor = [0] * (MAX_POSITIONS_ON_BOARD + 1) 

	#All positions from 1 to 6 can be reached from a single dice throw
	for  pos in range(1, 7):
		least_throws[pos] = 1
		predecessor[pos] = 0
	
	for  pos in range(7, MAX_POSITIONS_ON_BOARD+1):
		min_throws = MAX_POSITIONS_ON_BOARD

		#Find how many dice throws are needed to reach pos from any of 
		#the 6 previous cells
		for  i in range(1, 7):
			prev_pos = pos - i

			if (is_snake[prev_pos]):
				continue

			#Pick the minimum throws needed from the 6 previous cells
			if (least_throws[prev_pos] + 1 < min_throws) :
				min_throws = least_throws[prev_pos] + 1
				predecessor[pos] = prev_pos
			

		#Suppose we are at pos = 14 and ladder[14] = 4, then there is a ladder
		#from 4 to 14. So number of dice throws needed to reach 14 = number of 
		#dice throws needed to reach position 4
		ladder_start_pos = ladder[pos]
		if (ladder_start_pos != -1) :
			if (least_throws[ladder_start_pos] < min_throws) :
				min_throws = least_throws[ladder_start_pos]
				predecessor[pos] = ladder_start_pos
			
		least_throws[pos] = min_throws

	return least_throws[MAX_POSITIONS_ON_BOARD], predecessor

Longest increasing subsequence

admin / / Algorithms, Dynamic Programming

© Parineeth M R

Question 56. Find the longest increasing subsequence in an unsorted array of numbers

Consider the sequence A = {30, 40, 20, 70, 10}. The longest increasing subsequence is {30, 40, 70}. Here we are considering a strictly increasing longest subsequence and so a number can be present only once in the longest increasing subsequence even if it occurs several times in the original sequence. To solve the problem, we use dynamic programming as follows:

1.) We make use of an array called seq_length where seq_length[i] stores the length of the longest increasing subsequence ending at the position i. For instance seq_length[3] stores the length of longest subsequence from 0th to 3rd position, i.e. for the region {30, 40, 20, 70} in the above example. We initialize seq_length array with 1 at each position since each number itself forms a sequence of size 1 by itself.

2. We then compute the seq_length[i] from position 1 onwards using the formula:
seq_length[i] = 1 + max(seq_length[j]) where j < i and A[j] < A[i]

3. Once we have computed sequence lengths for all positions, then the maximum value in the seq_length array gives the length of the longest increasing subsequence. In our example, the maximum value in the seq_length array is 3. So length of longest increasing subsequence is 3.

The time complexity of this approach is O(n2).

C/C++


/*
a: array in which we need to find the longest increasing sequence
n: number of elements in the array. Should be >= 1
lis: the longest increasing sequence is returned in this array
Return value: length of the longest increasing sequence
*/
int find_lis(int a[], int n, int lis[])
{
	/*seq_length stores length of LIS for each position of array a*/
	int *seq_length = (int*) calloc(n, sizeof(int));

	/*prev_ix stores the index of previous element in the LIS sequence*/
	int *prev_ix = (int*) calloc(n, sizeof(int));

	int i, j, lis_length, lis_end;

	/*Each element by itself forms a sequence of length 1*/
	for (i = 0; i < n; ++i)
		seq_length[i] = 1;

	/*Find the LIS for each position in array a*/
	for (i = 1; i < n; ++i) {
		for (j = 0; j < i; ++j) {
			if ( a[j] < a[i] && seq_length[i] < seq_length[j] + 1 ) {
				seq_length[i] = seq_length[j] + 1;
				prev_ix[i] = j;
			}
		}
	}

	/*The longest LIS amongst all positions of array a will be the LIS  
	for the whole array*/
	lis_length = 1;
	lis_end = 0;
	for (i = 1; i < n; ++i) {
		if (lis_length < seq_length[i]) {
			lis_length = seq_length[i];
			lis_end = i;
		}
	}

	/*Use the prev_ix array to reconstruct the LIS for the whole array
	lis_end has the index of the last element in the LIS for whole array*/
	j = lis_end;
	for (i = lis_length - 1; i >= 0; --i) {
		lis[i] = a[j];
		j = prev_ix[j];
	}
	
	free(seq_length);
	free(prev_ix);

	return lis_length;
}

Java


/*a: array in which we need to find the longest increasing sequence.
	Should have atleast 1 element
Return value: array having the longest increasing sequence is returned
*/
public static int[] findLis(int[] a) {
	int n = a.length;

	/*seqLength stores length of LIS for each position of array a*/
	int[] seqLength = new int[n];

	/*prevIx stores the index of previous element in the LIS sequence*/
	int[] prevIx = new int[n];


	/*Each element by itself forms a sequence of length 1*/
	int i, j;
	for (i = 0; i < n; ++i)
		seqLength[i] = 1;

	/*Find the LIS for each position in array a*/
	for (i = 1; i < n; ++i) {
		for (j = 0; j < i; ++j) {
			if ( a[j] < a[i] && seqLength[i] < seqLength[j] + 1 ) {
				seqLength[i] = seqLength[j] + 1;
				prevIx[i] = j;
			}
		}
	}

	/*The longest LIS amongst all positions of array a will be the LIS
	for the whole array*/
	int lisLength = 1;
	int lisEnd = 0;
	for (i = 1; i < n; ++i) {
		if (lisLength < seqLength[i]) {
			lisLength = seqLength[i];
			lisEnd = i;
		}
	}

	
	int[] lis = new int[lisLength]; 

	/*Use the prevIx array to reconstruct the LIS for the whole array
	lisEnd has the index of the last element in the LIS for whole array*/
	j = lisEnd;
	for (i = lisLength - 1; i >= 0; --i) {
		lis[i] = a[j];
		j = prevIx[j];
	}

	return lis;
}

Python


#a: list in which we need to find the longest increasing sequence
#	should have at least 1 element
#Return value: list having the longest increasing sequence is returned
def find_lis(a) :
	n = len(a)

	#seq_length stores length of LIS for each position of list a
	#Each element by itself forms a sequence of length 1
	seq_length = [1 for i in range(0, n)]

	#prev_ix stores the index of previous element in the LIS sequence
	prev_ix = [0] * n

	#Find the LIS for each position in list a
	for  i in range(1, n):
		for  j in range(0, i):
			if ( a[j] < a[i] and seq_length[i] < seq_length[j] + 1 ) :
				seq_length[i] = seq_length[j] + 1
				prev_ix[i] = j
			
	#The longest LIS amongst all positions of list a will be the LIS 
	#for the whole list 
	lis_length = 1
	lis_end = 0
	for  i in range(1, n):
		if (lis_length < seq_length[i]) :
			lis_length = seq_length[i]
			lis_end = i
		
	lis = [0] * lis_length

	#Use the prev_ix list to reconstruct the LIS for the whole list
	#lis_end has the index of the last element in the LIS for whole list
	j = lis_end
	for  i in range(lis_length - 1, -1,-1):
		lis[i] = a[j]
		j = prev_ix[j]
	
	return lis

Coin change problem

admin / / Algorithms, Dynamic Programming

© Parineeth M R

Question 55. Given a set of coin denominations, find the change for a given amount using the least number of coins. For instance, suppose the coin denominations are 4¢, 5¢ and 7¢, then to get 13¢ using the least number of coins, we need to pick two 4¢ coins and one 5¢ coin.

Let us say that coin denominations are 1¢, 5¢ and 25¢. We can use a greedy approach as follows – Pick the maximum number of coins with the highest denomination and then the maximum number of coins with the next highest denomination and so on. So if we have to pick the change for 58¢, we pick two 25¢, then one 5¢ and finally three 1¢. So we use a total of 6 coins. Greedy approach produces the optimal result for this set of coin denominations. However, given any arbitrary set of coin denominations, the greedy approach will fail for many cases. For instance let the denominations be 1¢, 3¢, 4¢ and 5¢. If we use the greedy approach to get 7¢, we use one 5¢ and two 1¢ thereby requiring three coins. However the optimal solution needs only two coins (one 3¢ and one 4¢).

To solve the problem for any possible coin denominations, we use dynamic programming. We first solve the minimum number of coins needed for the amount of 1¢, then for the amount of 2¢ and so on till we reach the required amount. To compute the minimum number of coins for a higher amount, we make use of the already computed minimum number of coins for lower amounts. The formula used is

If amount = 0, minNumCoins(0) = 0

If amount > 0, minNumCoins(amount) = minimum of { 1 + minNumCoins(amount – denomination)} for all denominations which are less than or equal to the amount

For instance, let the denominations be 1¢, 3¢, 4¢ and 5¢. Using the formula above, minNumCoins[0¢] = 0 coins. The table below shows how the calculation is done for minNumCoins for 1¢, 2¢ and 3¢

So minNumCoins(1¢) = 1, minNumCoins(2¢) = 2 and minNumCoins(3¢) = 1. Similarly we find that minNumCoins(4¢) = 1 and minNumCoins(5¢) = 1. The calculations for 6¢ and 7¢ are shown below

So the minimum number of coins for 7¢ is 2 coins. If the final amount is m and there are n denominations, the time complexity of this approach is O(mn).

C/C++


/*
denom: array having the coin denominations. Should have atleast 1 element
num_denom: number of denominations
final_amount: amount for which change has to be obtained
Return value: Minimum number of coins needed to represent final_amount
*/
int find_min_coins(int denom[], int num_denom, int final_amount) 
{
	/*Array for storing the minimum number of coins for an amount*/
	int *min_num_coins = (int*) malloc( (final_amount+1) * sizeof(int));
	
	/*Array for storing the coin denomination chosen for an amount*/
	int *chosen_denom = (int*) malloc( (final_amount+1) * sizeof(int));
	int i, cur_amt, smaller_amt, result;
		
	min_num_coins[0] = 0;
	for (cur_amt = 1; cur_amt <= final_amount; cur_amt++) {
		min_num_coins[cur_amt] = MAX_INT_VALUE;
		for (i = 0; i < num_denom; ++i) {
			if (denom[i] <= cur_amt) {
		
				smaller_amt = cur_amt - denom[i];

				if (1 + min_num_coins[smaller_amt] < 
						min_num_coins[cur_amt]) {
					min_num_coins[cur_amt] = 
						1 + min_num_coins[smaller_amt];
					chosen_denom[cur_amt] = denom[i];
				}
			}
		}
	}
	
	result = min_num_coins[final_amount];
	printf("Minimum number of coins = %d\n", result);

	/*print the chosen denominations to get the final amount*/
	cur_amt = final_amount;
	while (cur_amt > 0) {
		printf("%d ", chosen_denom[cur_amt]);
		cur_amt = cur_amt - chosen_denom[cur_amt];
	}
	printf(" = %d\n", final_amount);

	free(min_num_coins);
	free(chosen_denom);
	return result;
}

Java


/*denom: array having the coin denominations. Should have atleast 1 element
finalAmount: amount for which change has to be obtained
Return value: Minimum number of coins needed to represent finalAmount
*/
public static int findMinCoins(int[] denom, int finalAmount) {
	/*Array for storing the minimum number of coins for an amount*/
	int[] minNumCoins = new int[finalAmount + 1];

	/*Array for storing the coin denomination chosen for an amount*/
	int[] chosenDenom = new int[finalAmount + 1];

	minNumCoins[0] = 0;
	int curAmount;
	for (curAmount = 1; curAmount <= finalAmount; curAmount++) {
		minNumCoins[curAmount] = MAX_INT_VALUE;
		for (int curDenom : denom) {
			if (curDenom <= curAmount) {
				int smallerAmt = curAmount - curDenom;

				if (1 + minNumCoins[smallerAmt] < 
						minNumCoins[curAmount]) {
					minNumCoins[curAmount] = 
						1 + minNumCoins[smallerAmt];
					chosenDenom[curAmount] = curDenom;
				}
			}
		}
	}

	int result = minNumCoins[finalAmount];
	System.out.println("Minimum number of coins = " + result);

	/*print the chosen denominations to get the final amount*/
	curAmount = finalAmount;
	while (curAmount > 0) {
		System.out.print(chosenDenom[curAmount] + " ");
		curAmount = curAmount - chosenDenom[curAmount];
	}
	System.out.println(" = " + finalAmount);

	return result;
}

Python


#denom: list having the coin denominations. Should have at least 1 element
#final_amount: amount for which change has to be obtained
#Return value: Minimum number of coins needed to represent final_amount
def find_min_coins(denom, final_amount) :
	#List for storing the minimum number of coins for an amount
	min_num_coins = [0] * (final_amount + 1)

	#List for storing the coin denomination chosen for an amount
	chosen_denom = [0] * (final_amount + 1)
	
	min_num_coins[0] = 0
	for  cur_amt in range(1, final_amount+1):
		min_num_coins[cur_amt] = MAX_INT_VALUE
		for  cur_denom in denom:
			if (cur_denom <= cur_amt) :
	
				smaller_amt = cur_amt - cur_denom

				if (1 + min_num_coins[smaller_amt] < 
						min_num_coins[cur_amt]) :
					min_num_coins[cur_amt] = (1 + 
						min_num_coins[smaller_amt])
					chosen_denom[cur_amt] = cur_denom
	

	result = min_num_coins[final_amount]
	print('Minimum number of coins = {}'.format(result) )

	#print the chosen denominations to get the amount
	cur_amt = final_amount
	while (cur_amt > 0) :
		print('{} '.format(chosen_denom[cur_amt]) , end='')
		cur_amt = cur_amt - chosen_denom[cur_amt]
	print(' = {}'.format(final_amount) )

	return result

Maximum Continuous Sum

admin / / Algorithms, Dynamic Programming

© Parineeth M R

Question 54. Find the maximum continuous sum in an array

An array can have positive and negative elements in it. We have to find a subset of contiguous elements in the array whose sum is the maximum. Let the maximum continuous sum be represented as MCS

In the brute force approach, we pick an element and then go on adding its right neighbors one by one to find the maximum contiguous sum starting at that element. We then repeat the process for all elements in the array to find the MCS across all elements. The time complexity of the brute force approach is O(n2).

However it is possible to find the MCS in O(n) time using kadane’s algorithm. This algorithm works for all cases (including the case where all the elements are negative). We maintain the variable max_local which will store the sum of the neighboring elements in the current window. The algorithm is described below:

1. Choose the first element and initialize max_local to the first element.

2. Traverse through the remaining elements. If the result of adding max_local to the current element is greater than current element, then add the current element to max_local and keep continuing the window. If however the result of adding max_local to the current element is less than the current element, then start a fresh window that starts at the current element and initialize max_local to the current element.

3. The maximum value of max_local across all elements will be the MCS of the array.

Let A = {4, -9, 5, 6 , 1} . max_local is initialized to 4. The remaining calculations are shown in the table below

C/C++


/* 
a: the array of numbers for which the MCS should be found,
length: number of elements. Should >= 1
mcs_start_pos: the starting array index of the MCS is returned here
mcs_end_pos: the ending array index of the MCS is returned here 
Return value: Maximum continous sum of the elements 
*/
int kadane_mcs(int a[], int length, int *mcs_start_pos, int *mcs_end_pos) {
	int i, max_local, max_global;
	int cur_start_pos;

	*mcs_start_pos = *mcs_end_pos = 0;
	cur_start_pos = 0; /*store the start position of the current window*/

	max_local = max_global = a[0];

	/*Traverse from the second element onwards*/
	for (i = 1; i < length; ++i) {
		max_local = max(a[i], a[i] + max_local);
		if (max_local == a[i])
			cur_start_pos = i; /*start a new window here*/

		/*Find the global maximum*/
		if (max_local > max_global) {
			max_global = max_local;
			*mcs_start_pos = cur_start_pos;
			*mcs_end_pos = i;
		}
	}

	return max_global;
}

Java


/* a: array of numbers for which MCS should be found. 
	At least 1 element should be present
mcsStartPos: the starting array index of the MCS is returned here
mcsEndPos: the ending array index of the MCS is returned here 
Return value: Maximum continous sum of the elements 
*/
public static int kadaneMcs(int[] a, Int mcsStartPos, Int mcsEndPos) {
	int length = a.length;
	int curStartPos = 0; /*store the start position of the current window*/
	int maxLocal = a[0], maxGlobal = a[0];
	mcsStartPos.value = mcsEndPos.value = 0;

	/*Traverse from the second element onwards*/
	for (int i = 1; i < length; ++i) {
		maxLocal = Math.max(a[i], a[i] + maxLocal);
		if (maxLocal == a[i])
			curStartPos = i;/*start a new window here*/

		/*Find the global maximum*/
		if (maxLocal > maxGlobal) {
			maxGlobal = maxLocal;
			mcsStartPos.value = curStartPos;
			mcsEndPos.value = i;
		}
	}

	return maxGlobal;
}

Python


#a: list of numbers for which MCS should be found. size of a >= 1
#Return value:  1. Maximum continuous sum of the elements , 
#		2. the starting list index of the MCS 
#		3. the ending list index of the MCS 
def kadane_mcs(a) :
	length = len(a)

	mcs_start_pos = mcs_end_pos = 0
	cur_start_pos = 0 #store the start position of the current window

	max_local = max_global = a[0]

	#Traverse from the second element onwards
	for  i in range(1, length):
		max_local = max(a[i], a[i] + max_local)
		if (max_local == a[i]):
			cur_start_pos = i #start a new window here

		#Find the global maximum
		if (max_local > max_global) :
			max_global = max_local
			mcs_start_pos = cur_start_pos
			mcs_end_pos = i

	return max_global, mcs_start_pos, mcs_end_pos