Dynamic Programming

 Dynamic Programming (DP) is an algorithmic technique for solving an optimization problem by breaking it down into simpler subproblems and utilizing the fact that the optimal solution to the overall problem depends upon the optimal solution to its subproblems.

Let’s take the example of the Fibonacci numbers. As we all know, Fibonacci numbers are a series of numbers in which each number is the sum of the two preceding numbers. The first few Fibonacci numbers are 0, 1, 1, 2, 3, 5, and 8, and they continue on from there.

If we are asked to calculate the nth Fibonacci number, we can do that with the following equation,

Fib(n) = Fib(n-1) + Fib(n-2), for n > 1

As we can clearly see here, to solve the overall problem (i.e. Fib(n)), we broke it down into two smaller subproblems (which are Fib(n-1) and Fib(n-2)). This shows that we can use DP to solve this problem.

1. Overlapping Subproblems 

Subproblems are smaller versions of the original problem. Any problem has overlapping sub-problems if finding its solution involves solving the same subproblem multiple times. Take the example of the Fibonacci numbers; to find the fib(4), we need to break it down into the following sub-problems:

Recursion tree for calculating Fibonacci numbers

We can clearly see the overlapping subproblem pattern here, fib(2) has been evaluated twice and fib(1) has been evaluated three times.

2. Optimal Substructure Property 

Any problem has optimal substructure property if its overall optimal solution can be constructed from the optimal solutions of its subproblems. For Fibonacci numbers, as we know,

Fib(n) = Fib(n-1) + Fib(n-2)

This clearly shows that a problem of size ‘n’ has been reduced to subproblems of size ‘n-1’ and ‘n-2’. Therefore, Fibonacci numbers have optimal substructure property.

 

Dynamic Programming Methods 

DP offers two methods to solve a problem.

1. Top-down with Memoization 

In this approach, we try to solve the bigger problem by recursively finding the solution to smaller sub-problems. Whenever we solve a sub-problem, we cache its result so that we don’t end up solving it repeatedly if it’s called multiple times. Instead, we can just return the saved result. This technique of storing the results of already solved subproblems is called Memoization.

2. Bottom-up with Tabulation 

Tabulation is the opposite of the top-down approach and avoids recursion. In this approach, we solve the problem “bottom-up” (i.e. by solving all the related sub-problems first). This is typically done by filling up an n-dimensional table. Based on the results in the table, the solution to the top/original problem is then computed.

Tabulation is the opposite of Memoization, as in Memoization we solve the problem and maintain a map of already solved sub-problems. In other words, in memoization, we do it top-down in the sense that we solve the top problem first (which typically recurses down to solve the sub-problems).

Let us now look at some problems solved with Dynamic Programming.

• 0/1 Knapsack Using DP
• Matrix Chain Multiplication Using DP
• Maximum-Minimum Using DP
• Fibonacci Using DP 

Check out more articles.

 

Fibonacci Numbers Using Dynamic Programming

 The following code illustrates the implementation of Fibonacci Numbers using the Dynamic Programming concept. Here we have used two basic principles of DP that is optimal substructure and overlapping behaviour to solve the problem. 

The time complexity of problem is O(n2) and space complexity is O(n) as we are using a 1-d Array.

//Fibonacci Series using Dynamic Programming 

#include<stdio.h> 

int fib(int n) 

{

/* Declare an array to store Fibonacci numbers. */

int f[n+2]; // 1 extra to handle case, n = 0 

int i; 

/* 0th and 1st number of the series are 0 and 1*/

f[0] = 0; 

f[1] = 1; 

for (i = 2; i <= n; i++) 

{ 

    /* Add the previous 2 numbers in the series 

        and store it */

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

} 

return f[n]; 

} 

int main () 

{ 

int n = 9; 

printf("%d", fib(n)); 

getchar(); 

return 0; 

} 

C program for finding linear variables using Extended Euler's GCD method

#include<stdio.h>

int gcdExtended(int a, int b, int *x, int *y) 

{ 

    // Base Case 

    if (a == 0) 

    { 

        *x = 0; 

        *y = 1; 

        return b; 

    } 

  

    int x1, y1; // To store results of recursive call 

    int gcd = gcdExtended(b%a, a, &x1, &y1); 

  

    // Update x and y using results of recursive 

    // call 

    *x = y1 - (b/a) * x1; 

    *y = x1; 

  

    return gcd; 

} 

  

// Driver Program 

int main() 

{ 

    int x, y; 

    int a ,b;

    printf("\nEnter the value of a and b: ");

    scanf("%d %d",&a,&b);

    int g = gcdExtended(a, b, &x, &y); 

    printf("gcd(%d, %d) = %d", a, b, g);

    printf("\nThe value of x and y are %d %d ",x,y); 

    return 0; 

}

C program for finding gcd using Euler's GCD

//Program to demonstrate the Eucleidian method of solving for GCD

#include <stdio.h>

int gcd(int a,int b)

{

    if(b==0)

        return a;

    return gcd(b,a%b);

}

int main()

{

    int a,b;

    printf("\nEnter the two nos.\n");

    scanf("%d %d",&a,&b);

    int max,min;

    max=(a>b)?a:b;

    min=(a<b)?a:b;

    printf("The GCD of two nos. is = %d",gcd(max,min));

}

C program for Double Ended Linked List

//doubly linked list

#include<stdio.h>

#include<stdlib.h>

typedef struct list 

{

    int data;

    struct list *next;

    struct list *prev;

}nd;

void ins_beg(nd **ptr)

{

    nd *cur=(nd*)malloc(sizeof(nd));

    printf("\nEnter the data : ");

    scanf("%d",&cur->data);

    if((*ptr)==NULL)

    {

        (*ptr)=cur;

        cur->prev=(*ptr);

        cur->next=NULL;

    }

    else 

    {

        cur->next=(*ptr);

        (*ptr)->prev=cur;

        (*ptr)=cur;

        cur->prev=(*ptr);

    }

}

void ins_end(nd **ptr)

{

    nd *cur=(nd*)malloc(sizeof(nd));

    printf("\nEnter the data : ");

    scanf("%d",&cur->data);

    if((*ptr)==NULL)

    {

        (*ptr)=cur;

        cur->prev=(*ptr);

        cur->next=NULL;

    }

    else 

    {

        nd *trav=(*ptr);

        while((trav->next)!=NULL)

        {

            trav=trav->next;

        }

        cur->next=NULL;

        trav->next=cur;

        cur->prev=trav;

    }

}

void traversal_from_front(nd *ptr)

{

    printf("\nDisplaying list: -  ");

    while(ptr!=NULL)

    {

        printf("%d ",ptr->data);

        ptr=ptr->next;

    }

}

void reversal(nd **ptr)

{

    nd *cur=(*ptr);

    nd *tmp=NULL;

    int s=0;

    while(cur!=NULL)

    {   

        if(s==0)

        {

            tmp=NULL;   //for first node make its next NULL

        }

        else

        {

            tmp=cur->prev;  //continue reversing directions

        }

        cur->prev=cur->next;

        cur->next=tmp;

        cur=cur->prev;

        s++;

    }

    if(tmp!=NULL)

    {

        (*ptr)=tmp->prev;   

    }

}

int main(void)

{

    nd *ptr;

    ptr=NULL;

    int c=3;

    while(c>0)

    {

        ins_beg(&ptr);

        traversal_from_front(ptr);

        c--;

    }    

    reversal(&ptr);

    traversal_from_front(ptr);

}

C program for Djikstra Algorithm

//Single source shortest path djisktra

#include <stdio.h>
#include <stdlib.h>

int cost[6][6]={{0,2,4,0,0,0},{0,0,1,7,0,0},{0,0,0,0,3,0},{0,0,0,0,2,1},{0,0,0,0,5,0},{0,0,0,0,0,0}};
int node[6]={0,9999,9999,9999,9999,9999};

void compute(int n,int src,int dest)
{
    if(src==dest)
        return;

    int j=0;

    for(j=src;j<n;j++)
    {
        if(j==src)
            continue;
        if(cost[src][j]!=0)
        {
            int s=cost[src][j]+node[src];
            if(s<node[j])  //Perform relaxation
            {
                node[j]=s;
            }
        }
        compute(n,j,dest);
    }

}

int main(void)
{
    /*int n;
    printf("Enter the no. of vertex: ");
    scanf("%d",&n);

    int i=1;
    int j=1;

    //If no path exists enter 0
    for(;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            printf("\nWeight for %d to %d :",i,j);
            scanf("%d",&cost[i-1][j-1]);
        }
    }

    int src,dest;
    printf("\nEnter the source node: ");
    scanf("%d",&src);
    printf("\nEnter the destination node: ");
    scanf("%d",&dest);

    //set source node to 0 only all others be 9999
    for(i=0;i<n;i++)
    {
        if(i==src)
            node[i]=0;
        else
            node[i]=9999;
    }*/

    int n=6;  
   
    int src=0;
    int dest=5;

    compute(n,src,dest);

    int i;
    for(i=0;i<n;i++)
    {
        printf("%d ",node[i]);
    }
}

C program for Double Ended Queue

#include<stdio.h>

#include<stdlib.h>

typedef struct node 

{

    int data;

    struct node *next;

}nd;

void disp(nd *root)

{

    printf("\nDisplaying linked list  :-   ");

    if(root==NULL)

        printf("List is empty");

    else 

    {

        nd *head=root;

        do

        {

            printf("%d ",root->data);

            root=root->next;

        } 

        while ((root)!=head);

    }

        

}

void ins_beg(nd **root)

{

    nd *ptr=(nd*)malloc(sizeof(nd*));

    printf("\nEnter the data:- ");

    int no;

    scanf("%d",&no);

    ptr->data=no;

    

    //Root is null

    if((*root)==NULL)

    {

        (*root)=ptr;

        ptr->next=(*root);

    }

    //List is not empty

    else

    {

        nd *prev_head=(*root);  //Stores previous root pointer

        ptr->next=(*root);

        (*root)=ptr;

        nd *cur=(*root);

        do

        {

            cur=cur->next;

        } while ((cur->next)!=prev_head);

        cur->next=(*root);

    }

}

void ins_end(nd **root)

{

    nd *ptr=(nd*)malloc(sizeof(nd*));

    printf("\nEnter the data:- ");

    int no;

    scanf("%d",&no);

    ptr->data=no;

    

    //Root is null

    if((*root)==NULL)

    {

        (*root)=ptr;

        ptr->next=(*root);

    }

    //List is not empty

    else

    {

        nd *prev_head=(*root);  //Stores previous root pointer

        

        nd *cur=(*root);

        do

        {

            cur=cur->next;

        } while ((cur->next)!=prev_head);

        cur->next=ptr;

        ptr->next=prev_head;        

    }

}

int main(void)

{

    int c=6;

    nd *root=NULL;

    while(c>0)

    {

        if(c%2==0)

            ins_beg(&root);

        else

            ins_end(&root);

        disp(root);

        c--;

    }

}

C program for Circular Linked List

#include<stdio.h>

#include<stdlib.h>

typedef struct node 

{

    int data;

    struct node *next;

}nd;

void disp(nd *root)

{

    printf("\nDisplaying linked list  :-   ");

    if(root==NULL)

        printf("List is empty");

    else 

    {

        nd *head=root;

        do

        {

            printf("%d ",root->data);

            root=root->next;

        } 

        while ((root)!=head);

    }

        

}

void ins_beg(nd **root)

{

    nd *ptr=(nd*)malloc(sizeof(nd*));

    printf("\nEnter the data:- ");

    int no;

    scanf("%d",&no);

    ptr->data=no;

    

    //Root is null

    if((*root)==NULL)

    {

        (*root)=ptr;

        ptr->next=(*root);

    }

    //List is not empty

    else

    {

        nd *prev_head=(*root);  //Stores previous root pointer

        ptr->next=(*root);

        (*root)=ptr;

        nd *cur=(*root);

        do

        {

            cur=cur->next;

        } while ((cur->next)!=prev_head);

        cur->next=(*root);

    }

}

void ins_end(nd **root)

{

    nd *ptr=(nd*)malloc(sizeof(nd*));

    printf("\nEnter the data:- ");

    int no;

    scanf("%d",&no);

    ptr->data=no;

    

    //Root is null

    if((*root)==NULL)

    {

        (*root)=ptr;

        ptr->next=(*root);

    }

    //List is not empty

    else

    {

        nd *prev_head=(*root);  //Stores previous root pointer

        

        nd *cur=(*root);

        do

        {

            cur=cur->next;

        } while ((cur->next)!=prev_head);

        cur->next=ptr;

        ptr->next=prev_head;        

    }

}

int main(void)

{

    int c=6;

    nd *root=NULL;

    while(c>0)

    {

        if(c%2==0)

            ins_beg(&root);

        else

            ins_end(&root);

        disp(root);

        c--;

    }

}