Greedy approach vs Dynamic Programming

Greedy approach and Dynamic programming both are used for solving optimisation problems. However often we need to use DP since optimal solution cannot be guaranteed by a greedy algorithm.

Consider Knapsack problem

We could solve it by brute-force, by generating all 2^n possibilities of choosing a subset of n items and selecting the best one. But time complexity of this solution is exponential \Omega{(2^n)} (Big Omega means lower bound.)

Greedy algorithm also fails to find the solution for 0/1 Knapsack problem.

For Dynamic programming solution: https://www.onlycode.in/knapsack-problem-dynamic-programming/

Dynamic Programming

DP algorithms uses the fact that an optimal solution to a problem of size n is composed of an optimal solution to a problem of size n‘ < n and uses this to build the solution bottom up ie from smallest problem to required size.

Greedy Algorithms

Greedy algorithm are looking at a local point and doing some choice based with the data at this point. For some problems, this local choice leads to an optimal solution.

Some examples

Djikstra’s algorithm

Uses greedy approach to find the shortest paths between nodes in a graph, which may represent, road networks.

Bellman-ford algorithm

Uses dynamic programming as an algorithm to compute shortest paths from a single source vertex to all of the other vertices in a weighted digraph.

Dynamic Programming (Two approaches)

DP ~ “careful brute force”

DP ~ subproblems + reuse

Bottom up (Tabulation) : When we first look at the smaller subproblems and then solve large subproblems using solution to smaller sub-problems.

Top-down (Memoization) : It is similar to recursion but store the solutions to subproblems. It solves the problem in a natural manner (recursion) and check if you have calculated the solution to subproblem before.

Example – Fibonacci

Fibonacci sequence is a sequence such that each number is the sum of the two preceding ones, starting from 0 and 1.

1 1 2 3 5 8 13 21….and so on

Let’s start with Bottom up

Optimal substructure:

F_n = F_{n-1} + F_{n-2}

Coding solution:

int dp[N+1];
int solve(int N) {
  //Base cases
  dp[0] = 0;
  dp[1] = 1;
  for (int i=2; i<=N; i++) {
    dp[i] = dp[i-1] + dp[i-2];
  }
  return dp[N];
}

Top down approach

Coding solution:

int dp[N+1] = {0};
int solve(int N) {
  if (N <= 1) {
      return N;
  } 
  if (dp[N] == 0) {
    dp[N] = solve(N-1) + solve(N-2);
  }
  return dp[N];
}

Leave a Reply

Your email address will not be published.