Dynamic Programming Basics

Introduction

Dynamic programming is one of the problem solving paradigms where we try to find a solution by breaking the larger problem into subproblems, and exploit the fact that the optimal solution to the problem depends upon the optimal solution to its subproblems.

The following two charateristics suggest that the given problem can be solved using dynamic programming :

  1. Overlapping subproblems : It ensures that the given problem can be divided into a number of subproblems of similar type, but of smaller size than the original one.

  2. Optimal Substructure Property : It ensures that the optimal solution to the problem can be formulated from the optimal solution to its subproblems.

We can also compare with a greedy approach that the local optimum choice may not always be the global optimal choice. An example is finding the shortest path between two cities. A local junction may appear shorter but turn out to be long, while a longer junction may turn out to be a shorter route over all.

Dynamic Programming has two methods that can be used according to the problem at hand.

Top-Down Approach

A top-down DP approach tries to solve the bigger problem by recursively finding the solution to smaller problems while also storing local solutions in a look-up table such that those are not computed each time. This technique is called Memo-ization

An example :-

Problem statement : Let us define a recurrence .

Given find the term of the recurrrence ?

Solution using Top - Down Approach :

    int F[MAXSIZE] ;
    // set F to some unique value like -1 in this case.
    int solve(int n){
        if(n < 3){
            return 7 ;      // recurrence defination
        }
        int &ret = F[n] ;   // cache technique
        if(ret != -1)       // absence of -1 indicate that this is already computed 
            return ret ;            // use this computed result 
        ret = solve(n-3) + solve(n-1) ;         // compute otherwise
        return F[n] = ret ;      // final return computed answer
    }

Bottom Up Approach

This technique is the opposite of the former and here we start from the smallest solution and go up to the required solution. It is assumed that coming up with a bottom up solution is relatively easy.

An example :-

Problem statement : Let us define a recurrence .

Given find the term of the recurrrence ?

Solution using Bottom - Up Approach :

    int F[MAXSIZE] ;
    int solve(int n){
        F[0] = F[1] = F[2] = 7 ;    // recurrence definition
        for(int i=3;i<=n;i++)
            F[i] = F[i-1] + F[i-3] ;    // recurrence definition
        return F[n] ;
    }

Uses

Dynamic programming can be used to solve

  • Recurrence Relations
  • Optimization Problems
 
Related challenge for Dynamic Programming Basics
Go to Top

Priority Queue

A priority queue is an Abstract data type, which has a queue-like behavior with a change that when you deque you can prioritize an element on some comparator. As an example, you can make a priority queue that returns the maximum or minimum element on each deque.

Priority queues are often implemented using Min/Max Heaps. Each insert happens with complexity due to heapify. And each deque is .

C ++ STL provides a priority queue container.

Sample Implementation in C ++ :

#include <iostream>
#include <queue> // library needs to be included
using namespace std ;
int main(){
    priority_queue<int> Q ; // by default it is maximum priority queue
    Q.push(10) ;  // insert 1st element
    Q.push(12) ;  // insert 2nd element
    Q.push(8) ;   // insert 3rd element
    Q.push(16) ;  // insert 4th element
    Q.push(10) ;  // insert 5th element
    cout << Q.top() << endl ;    // print maximum element in the current Q
    Q.pop() ;       // removing maximum element from current Q
    cout << Q.top() << endl ;    // print maximum element in the current Q
    Q.pop() ;       // removing maximum element from current Q
    cout << Q.top() << endl ;    // print maximum element in the current Q
    Q.pop() ;       // removing maximum element from current Q
    cout << Q.top() << endl ;    // print maximum element in the current Q
    Q.pop() ;       // removing maximum element from current Q
    cout << Q.top() << endl ;    // print maximum element in the current Q
    Q.pop() ;       // removing maximum element from current Q
    return 0 ;
}

/*
    output of the above program
    16
    12
    10
    10
    8
*/
 
Go to Top
  1. Challenge Walkthrough
    Let's walk through this sample challenge and explore the features of the code editor.1 of 6
  2. Review the problem statement
    Each challenge has a problem statement that includes sample inputs and outputs. Some challenges include additional information to help you out.2 of 6
  3. Choose a language
    Select the language you wish to use to solve this challenge.3 of 6
  4. Enter your code
    Code your solution in our custom editor or code in your own environment and upload your solution as a file.4 of 6
  5. Test your code
    You can compile your code and test it for errors and accuracy before submitting.5 of 6
  6. Submit to see results
    When you're ready, submit your solution! Remember, you can go back and refine your code anytime.6 of 6
  1. Check your score