What is dynamic programming?

What is Dynamic programming?

Dynamic programming is a way of solving bigger problems with the help of results of sub-problems. Difference between divide and conquer and dynamic programming is that in divide and conquer approach sub problems are mutually exclusive where as in dynamic programming sub problems are overlapping.

Conditions for application of dynamic programming approach

There are two properties which should be fulfilled by any problem to be classified as dynamic programming problem.
 
First is optimal structure. Problem should ask for the optimal value as result like maximum value for given weight, over maximum no of applications with given bandwidth etc and optimal solution of subproblems can be used to get optimal solution of bigger problem. Second, there should be overlapping sub problems, which can be used to derive the solution for the bigger problem.

There are two approaches in which dynamic programming can be used :

1. Bottom up approach 
In this, problem is divided into smaller problems and then smallest problem is solved and used upward to solve bigger problems.

2. Top down approach
When we have recursive relation like this T(n) = 2 T(n-1) + n, where subproblem is not significantly smaller than the original problem, and going down the recursion tree, many subproblems are same, it is better to store results of each problem we have seen till now and use them to calculate solution of subproblems, here subproblems already calculated are not again done. This technique is called as memoization.

Any dynamic programming problem can be solved using recursion, by reducing the candidate each time depending on the required output. However, that solution unnecessary solves already solved sub problems again and again leading to increase time complexity. In dynamic programming approach, we store the results of sub problems and each sub problem is evaluated only once. Hence in DP we trade time with space.
There are many problems which are good candidate for dynamic programming application. I have made a list of such problems and will code there one by one in my following posts.

1.  0-1 knapsack problem
2.  Longest increasing subsequence
3.  Longest palindrome sub string
4.  Matrix chain multiplication
5.  Longest common sub sequence.
6.  Coin change

0-1 knapsack problem using dynamic programming

0-1 Knapsack problem

0/1 Knapsack problem is a classic problem which is used to demonstrate application of greedy algorithm and dynamic programming. Greedy algorithm works for knapsack problem when partial weights are allowed but does not give optimal solution for 0/1 problem when partial weights are not allowed. In this post, as we are discussing 0/1 knapsack problem, we will focus on dynamic programming solution of it.

There are many flavors in which 0–1 Knapsack problem can be asked. Some are list below

1. A thief enters a museum and want to steal artifacts from there. Every artifact has a weight and value associated with it. Thief carries a knapsack (bag) which can take only a specific weight.
Problem is to find combination of artifacts thief takes, so that he gets maximum value and weight of all artifacts taken by him is less the capacity of his bag. Thief cannot take any artifact partially. Either he takes it or leaves it. Hence the problem is 0-1 knapsack.

2. Second flavor is : We have N files each having a size say Si. We have a total storage capacity of W bytes. For each file to be stored, re-computation cost is Vi. Problem is to store as files on storage that combined size of all files is less than W and their re-computation value is maximum. We can either store or leave a file. We cannot store partial file. Hence, this is a case of 0-1 knapsack problem.

0-1 Knapsack problem in mathematics terms:

There are N items <I1,I2,................In> each having a weight <w1,w2,...............wn>.
Each item has a value associated with it <v1,v2, ..........vn>
Given a limit W we have to find a subset of K items such that 
                  Sum (w1, w2..... wk) <= W  &
                  Sum (v1,v2,.........vk) is maximum.

Brute force method would try all subsets of set of items and see which one gives as the maximum value. This method would be of exponential order because there are 2^n subsets for a set with n elements.
Can we do better than this? For each item in set, there are two possibilities associated with it.
First, given item is included in the subset which is optimal. Then we need to find out all the items in remaining N-1 items which can optimize the sub problem for weight W-wk. Value of this item is added to candidate maximum value.

Second possibility is that item is not included into already optimal subset. In this case, find out items in remaining N-1 items which can optimize the the original problem. Value of this item is not added into candidate maximum value. So problem still remains with weight W and Value V but with N-1 items to be considered.
Inclusion or exclusion of an item depends on two conditions :

1. Weight of the item is less than the total weight, then can be included. If it weight is more than total weight, directly exclude it. 
2. Inclusion of item increases the value which was already there with K-1 items with W-Wk weight.

When remaining allowed weight is zero (case 1) or we have considered all items (case 2) , we have reached the solution.

0-1 knapsack problem: Dynamic programming Implementation

Going in implementation, we define a two dimensional array of size N * W. Element in this array can be interpreted as for a given value of W  w (w<W) and for a given number of items i (i < N),   best solution would be value of that element i.e array(i, w).

For i=0 and w=0, all the values will be zero. Hence first column and first row will be filled with all zero values. We would build on top of that.
For each item in set, we would check for maximum value we can get for weight w.  As explained in the analysis, based on its two conditions, we include or exclude the item.
We can easily keep track of which items are included in optimal structure by keeping boolean two dimensional array. Each element a[i,j] is true if for weight jth item was included.

#include <stdio.h>
 
int knapsack01(int w[], int v[], int N, int W){
 
  int table[N+1][W+1];
  int i, j;
 
  for(i=0;i<=N; i++){
     for(j=0; j<=W; j++){
        table[i][j]=0;
     }
  }
 
  for(i=0; i<=N; i++){
     for(j=0; j<=W; j++){
         if(i == 0 || j == 0){
            table[i][j] = 0;
         }
        /* Condition when item can be included
           We check if inclusion of this item leads to increase in 
           value.
           If without including this value, for this weight, value was 
           greater than including this item, then we would take previous
           value. */ 
        else if(w[i-1] <= j){
            table[i][j] = table[i-1][j] > (v[i-1] + \
              table[i-1][j-w[i-1]]) ? table[i-1][j] : \
                        v[i-1] + table[i-1][j-w[i-1]]; 
         }
         else{
              table[i][j] = table[i-1][j];
         }
 
       }
     }
     return table[N][W];   
}
int main(void) {
	int w[] = { 2,3,4,1,2 };
	int v[] = { 5,4,1,2,1 };
	int W = 10;
	int size = sizeof(w)/sizeof(w[0]);
	printf("Optimal Value : %d ", knapsack01(w, v, size, W));
	return 0;
}

One similar problem which can be solved with same approach is minimum number of coins to be used to get change of a particular amount.
I am skipping the whole analysis and directly pasting the code here.

#include <stdio.h>
 
int minimumCoins(int denominations[], int C, int n){
	int i,j;
	#define MAX_COINS C
	int M[C];
	for(i=0;i<=C;i++){
		M[i] = MAX_COINS;
	}
	M[0]=0;
	M[1]=1;
 
	for(i=2;i<=C; i++){
	    for(j=0;j<n;j++){
		if((i-denominations[j]) >=0 && M[i-denominations[j]]+1 < M[i])
		     M[i] = M[i-denominations[j]] +1;
		}
	}
	return M[C];    
}
int main(void) {
	int denominations[] = {1,2,3,4};
	int C = 10;
	int size = sizeof(denominations)/sizeof(denominations[0]);
	printf("Minimum number of coins required : %d", 
                minimumCoins(denominations, C, size));
	return 0;
}

Complexity of the dynamic programming implementation of knapsack problem is O(N *W). Space complexity is again O(N*W). It is thumb rule that we trade space for time in dynamic programming.

http://www.es.ele.tue.nl/education/5MC10/Solutions/knapsack.pdf

Longest increasing subsequence in array

Longest increasing subsequence problem

Given an array of integers, find longest increasing subsequence in it, increasing subsequence is set of elements of array such that if i<j then a[i] < a[j]. For example, in array [ 2,4,6,3,5,7,9 ], longest increasing subsequence is  [ 2,4,6,7,9 ] with length 5.

Brute force solution is to find all possible subsequences of an array and check each one of them for increasing subsequences and then output the longest one.  Number of subsequence of an array with length n is 2n. SO, solution has exponential complexity.

Can we do it in polynomial complexity? First of all, try to break problem into smaller and then work the solution up. To find longest subsequence till A[i], can solution till A[i-1] help?
Idea is to find if longest subsequence already present before a particular element A[i], can include A[i] and remains increasing subsequence.

Let’s say LIS[i] represent longest increasing subsequence till i.

LIS[i] = 1 + MAX(LIS[j]) for j = 0 to i-1 and A[j] < A[i]

Implementation wise, checking every element from start of the array to element under consideration, if A[j] is less than A[i], then A[i] can be part of the subsequence ending with  A[i]. So length of longest increasing sub sequence can be MAX of (length of sub sequence ending at j )+1.

Let’s work out an example. Array A = [2,4,6,3,5,7,9]

Initialize LIS[0] = 1, there is increasing subsequence of length 1 at index 0.

For i = 1, j will range from index 0 to 0. a[0] < a[1], hence LIS[1]=2 (MAX(LIS[0]) + 1 ).

For i = 2, j will vary from 0 to 1. Get max of LIS[0] and LIS[1] and 1 to it. MAX LIS till index 1 is 2. Hence, LIS[2] = 3 ( LIS[1] +1 )

For i = 3, j ranges from 0 to 2, Max LIS till index 3 will be LIS[3] = 2 because only a[0] is less than a[3]. Hence, longest subsequence till index 3 will have length as 2. LIS[3] = 2.

For i = 4, i.e.5; LIS[4] Max ( LIS[0], LIS[1], LIS[3] ) + 1  = 3, sequence may be [ 2,4,5 ] or [ 2,3,5 ]

For i = 5, LIS[5] = Max (LIS[0], LIS[1], LIS[2], LIS[3], LIS[4]) + 1 = 4; subsequence may be [ 2,4,5,7] or [ 2,3,5,7 ] or [ 2,4,6,7 ]

For i = 6, LIS[6] = Max (LIS[0], LIS[1], LIS[2], LIS[3], LIS[4], LIS[5]) + 1 = 5;  [ 2,4,5,7,9 ] or [ 2,3,5,7,9 ] or [ 2,4,6,7,9 ] being possible longest subsequence till index 6.

Find longest increasing subsequence (LIS)


#include <stdio.h>
#include <stdlib.h>
 
int maximumLIS(int a[], int end, int *lis){
	for (int i=0; i<end; i++){
		if( a[i] < a[end] && lis[i] > lis[end] )
			lis[end] = lis[i];
    }
    return lis[end];
}
 
int lis(int a[], int size){
 
    int *lis = (int *)malloc(sizeof(int)*size);
    lis[0] = 1;
 
    for(int i=1; i<size; i++){
    	lis[i] = 1 + maximumLIS(a,i,lis);
    }
 
    int result = lis[size-1];
    free(lis);
 
    return result;
}
 
 
int main(void) {
	// your code goes here
	int a[] = { 2,4,6,3,5,7,9 };
	int size = sizeof(a)/sizeof(a[0]);
 
	printf("Length of Longest increasing subsequence : %d",
                                      lis(a, size));
 
	return 0;
}

Algorithm to find longest increasing subsequence works in O(n2) in time complexity with O(N) space complexity.

There are many problems which are solved using finding longest increasing subsequence method. For example:
1.Given two river banks (visualization : two parallel lines), one bank has numbers written (1….n) in sorted order. On the other bank the numbers (1…n) are arranged randomly. A bridge can be formed from the ith point from bank 1 to ith point in bank 2. Find the max number of non-intersecting bridges you can form?
Just find longest increasing subsequence in non ordered number and that will be the solution.

2. Given a set of n types of rectangular 3-D boxes, where the ith box has height h(i), width w(i) and depth d(i) (all real numbers). You want to create a stack of boxes which is as tall as possible, but you can only stack a box on top of another box if the dimensions of the 2-D base of the lower box are each strictly larger than those of the 2-D base of the higher box.

Coming back to problem of longest increasing subsequence, complexity of brute force solution is exponential where as for dynamic programming approach is O(n2). Question is can we find longest increasing subsequence in nlogn complexity?

Longest increasing subsequence in nlogn)

Basic idea behind solution is to keep track of all active subsequences at a given point of time. Based on the current elements being consider, update these active lists. To understand this process, let’s work out an example.

A = {2,8,7}
Monotonically increasing subsequences are {2,8} and {2,7}

What if we add another element, 11 in this?

A = {2,8,7,11}
Monotonically increasing subsequences are {2,8,11} and {2,7,11}

What if new element 9 is added to array? What happens now? If we add it t0 subsequences, length of longest subsequence remains 3.

A = {2,8,7,11,9}
Monotonically increasing subsequences are {2,8,9} and {2,7,9}

Question is should we create new active subsequences with length 3 adding 9 to them or continue with 11 in them? Consider the next element is 10. At this point we know, that adding 9 to subsequence leads us to longer subsequences than keeping 11.

How do we decide when to replace and when to continue with the old element in subsequence?  We can add or replace current element A[i] to an existing sequence if there is an element A[j] (j > i) such that E < A[i] < A[j] or (E > A[i] < A[j] – for replace), E being the last element in subsequence. In above example, E = 11, A[i] = 9 and A[j] = 10.

What if A[i] is smaller than all elements in all subsequences? In this case, we have to create a new list and add A[i] into it. Whole idea is to maintain lists of increasing sequences and update them based  on new element.  Every time new element is to be added, scan all lists (for end elements) in decreasing order of their length. Below algorithm gives how to add, replace new element in existing list or to create a new list with it.

Longest increasing subsequence algorithm 

1. If A[i] is smallest among all end candidates of active lists, start new active list of length 1.
2. If A[i] is largest among all end candidates of active lists, clone the largest active list, and extend it by A[i].
3. If A[i] is in between, find a list with largest end element that is smaller than A[i]. Clone and extend this list by A[i]. 
4. Discard all other lists of same length as that of this modified list.

Longest increasing subsequence example

Let’s take an example and see how it works:
A = [ 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13 ].

A[0] = 0. Case 1. Since there are no active lists, create a new one.
Lists = [[0]].

A[1] = 8. Case 2. A[i] is greater than end elements of al lists, so select the longest one and clone it extend.
Lists [ [0], [0, 8]

A[2] = 4. A[i] is less than end of one of the list and greater than other. Find the list which has end element less than A[i], it’s [0]. Clone it, extend and discard all list with similar length lists.
List = [ [0], [0, 4] ].
[0, 8] is discarded

A[3] = 12. Same as A[1].
Lists = [ [0], [0, 4], [0, 4, 12] ]

A[4] = 2. Same as A[2], Clone the one with largest end which is less than A[i], extend it and discard all same length lists.
Lists = [ [0], [0, 2], [0,4,12]
[0, 4] is discarded.

A[5] = 10. Same as A[4]. Clone, extend and discard.
Lists = [ [0], [0, 2], [0,4,10] ]
[0, 4, 12] is discarded.

A[6] = 6. Same as A[5] Clone, extend and discard.
Lists = [ [0], [0, 2], [0,2,6] ]
[0, 4, 10] is discarded.

A[7] = 14. Same as A[1]. Clone and extend.
Lists = [ [0], [0, 2], [0,2,6],  [0,2,6,14] ]

A[8] = 1. Same as A[6]. Clone, extend and discard.
Lists = [ [0], [0,1], [0,2,6] [0,2,6,14]
[0, 2] is discarded

A[9] = 9. Same A[8]. Clone, extend and discard.
Lists = [ [0], [0,1], [0,2,6] [0,2,6,9] ].
[ 0, 2, 6, 14 ] is discarded.

A[10] = 5. Same as A[9]. Clone, extend and discard.
Lists = [ [0], [0,1], [0,2,5] [0,2,6,9]].
[ 0, 2, 6] is discarded.

A[11] = 13. Same as A[1]. Clone and extend.
Lists = [ [0], [0,1], [0,2,5] [0,2,6,9], [0,2,6,9,13]].

LIS is [ 0,2,6,9,13] with length of 5.

This looks like lot of things to be done just for maintaining list and there requires a lot of space to store all of these lists. There is an insight which helps do optimize all this stuff, observer that all we are using from lists are their end elements. We do not care what was prior to them in list. So, can we store just end elements of an auxiliary array and do operations on them? Size of this array in worst case will be n if arrays is sorted.

To extend the list, add another element in auxiliary array. To replace just overwrite the smallest element which is greater than current element. To find smallest element which is greater than current element, we use algorithm called ‘Ceiling’, which is modification of binary search.

To find length of longest subsequence, keep track of length of auxiliary array, because at the end, length of it will be length of LIS.

Implementation of longest increasing subsequence in nlogn

#include<stdio.h>
#include<stdlib.h>
 
int ceilElement(int a[],int start,int end,int key){
	while(end-start > 1){
		int mid = start +(end - start)/2;
		if(a[mid]>=key){
			end = mid;
		}
		else{
			start = mid;
		}
	}
	return end;
}
 
int longestIncreasingSubsequence(int input[], int size)
{
	if(!size)
		return 0;
 
	int a[size];
	int length=1;
 
	a[0] = input[0];
 
	for(int i=1; i<size; i++)
	{
	    if(input[i]< a[0])
		    a[0]=input[i];
	    else if(input[i]>a[length-1])
		    a[length++]=input[i];
	    else
		    a[ ceilElement(a,-1,length-1,input[i]) ]= input[i];
	}
	return length;
}
 
int main() {
	int a[]={0,8,4,12,2,10,6,14,1,9,5,13,1,7,15};
	int size =sizeof(a)/sizeof(a[0]);
 
	printf("Longest Increasing Sub-sequence is = %d",
                                 longestIncreasingSubsequence(a,size));
	return 0;
}

Complexity of algorithm to find longest increasing subsequence in nlogn is of course O(n log n) as for each element in array, it requires log n time to find ceiling of it and put it at correct position.

This article is influence by http://stackoverflow.com/questions/6129682/longest-increasing-subsequenceonlogn and comments provided by readers under these articles.

Please share if there is something missing or wrong in this article. We would love to correct it. Also, if you want to contribute and earn, please drop us a mail using contact us form.

Longest Palindromic Substring

Longest Palindromic Substring

Given a string S, find longest palindromic substring in S. For example, if S = ‘ABDCBABCBAA’, longest substring which is palindrome is “CBABC”.

Longest palindrome substring in a string can easily be found using brute force. Find all possible substrings for given string and check if that substring is palindrome or not. There are C(N,2) substring possible for a string of length N. Complexity of this method is O(N3).

With slight optimization, brute force solution can be O(N2).
Starting from each character in string and check on left and right side of the character till both character at left and right same. Once they differ, check if number of characters in substring centered character is greater than length of earlier palindrome substring. If current length is greater, update longest palindrome substring length and look for subsequent characters till the end of string.

Finding longest palindromic substring algorithm

MaxLength = 0
For each index c in string
    i = c-1
    j = c+1
    currentLength = 0
    While i greater than or equal to 0 and j less than length of string
       if string[i] == string[j]
          currentLength++
          j++;
          i-- 
       else
         if maxLength less than currentLength
            maxLength = currentLength

Repeat all steps in above Pseudo code, starting with 1 for i (not with zero). (For taking into account even length string).

#include <stdio.h>
#include <string.h>
 
#define true 1
#define false 0
 
int longestPalindrome(char *s){
 
  int i,j,k, n;
  int longestEnd =0, longestStart=0;
 
  n = strlen(s);
/* This is case which handles odd length string */
   for(i=0; i<n; i++){
       for(j=i-1, k=i+1; j>=0 && k<=n; ){
   /* If characters are equal, update left and right index. */
           if(s[j] == s[k] ){
                k++;
                j--;
           }
           else
                break;
       }
  /* Check if current sub-string length is greater 
    than earlier max, If yes, update it */
      if(longestEnd - longestStart < k-j)
      {
          longestEnd = k;
          longestStart = j;
      }
 }
/* This is case which handles even length string */
  for(i=1; i<n; i++){
       for(j=i, k=i+1; j>=0 && k<=n; ){
            if(s[j] == s[k] ){
                k++;
                j--;
            }
            else
                break;
       }
       if(longestEnd - longestStart < k-j)
       {
            longestEnd = k;
            longestStart = j;
       }
  }
  return longestEnd - longestStart - 1;
}
int main()
{
    char str[] = "ABCDCBEA";
    printf("\nLength is: %d\n", longestPalindrome( str ) );
    return 0;
}

Complexity of the above code is O(N2).

Finding longest palindromic substring with dynamic programming 

Can we do better than brute force solution? Fundamental for applying Dynamic programming to any problem is that it should satisfy two basic conditions : First, problems should be solved by solving it’s subproblems and second, solutions to those subproblems must overlap.

Coming back to over problem, can finding longest palindrome substring be sub-divided into smaller problems? If we find a palindrome substring in string with length N-1, what effect it has on string N? What if N =1?
Every character in itself is a palindrome string, string with length one is palindrome.

P(i,i) = TRUE

If N =2, string with two characters is palindrome if both characters are equal.

P(i,i+1) = TRUE if str[i] == str[i+1]

For each length L greater than 2 and less than N, find substring of length L starting with each index of substring.
So Palindrome(i,j) represents substring with L, with starting index as i and end index as j. How can we say that this substring is palindrome? If substring from i+1 to j-1 was palindrome i.e Palindrome(i+1,j-1) = TRUE and str[i] == str[j], then Palindrome(i,j) = TRUE. Store L as length and compare it with maximum length found so far.

P(i,j) = ( P(i+1, j-1) and str[i] == str[j] )

Table is filled starting from (0,0) to (n,n) and when table if filled, we have longest palindrome substring length in a given string. For sake of information, we can also store where does this palindrome substring starts in string.

#include <stdio.h>
#include <string.h>
 
#define true 1
#define false 0
 
int longestPalindrome(char * s) {
  int n = strlen(s);
 
  int longestBegin = 0;
  int maxLen = 1;
  int table[n+1][n+1];
  for (int i = 0; i <= n; i++) {
  	for (int j = 0; j <= n; j++) {
  		table[i][j] = false;
  	}
  }
  for (int i = 0; i < n; i++) {
    table[i][i] = true;
  }
  for (int i = 0; i < n-1; i++) {
    if (s[i] == s[i+1]) {
      table[i][i+1] = true;
      longestBegin = i;
      maxLen = 2;
    }
  }
  for (int len = 3; len <= n; len++) {
    for (int i = 0; i < n-len+1; i++) {
      int j = i+len-1;
      if (s[i] == s[j] && table[i+1][j-1]) {
        table[i][j] = true;
        longestBegin = i;
        maxLen = len;
      }
    }
  }
  return maxLen;
}

int main()
{
    char str[] = "ABCDCBE";
    printf("\nLength is: %d\n", longestPalindrome( str ) );
    return 0;
}

Complexity of dynamic programming approach is same as brute force algorithm and is O(N2), It also uses extra memory though in order O(N2).

Please share if there is something wrong or missing, we would love to hear from you.
If you want to contribute to the website, please contact us.