Dynamic Programming (DP)

Jan 16, 2022#dsa#dp#algorithms

Dynamic programming (DP) is an algorithmic optimization technique over recursion when we cahe the results of subproblems so that we don’t have to recompute them again and again. The core idea is to avoid repeated work by remembering partial results.

It is important for a problem to have BOTH following characteristics in order to be eligible to be solved using DP technique.

  • Overlapping subproblems: When solutions of the same subproblems are needed again and again. If not overlapping then it’s Divide and Conquer.
  • Optimal substructure: If optimal solution of the given problem can be obtained by using optimal solutions of its subproblems.

There are following two different ways to store the values so that these values can be reused:

  • Tabulation: Bottom-up, iterative, all entries are filled one by one.
  • Memoization: Top-down, recursive, entries are filled on demand.

DP combines the correctness of compelete search and efficiency of greedy algorithms to reduce time complexity from exponetial to polynomial.

  • Finding an optimal solution
  • Counting the number of solutions

Usually creativity is required before we can recognize that a particular problem can be cast effectively as a dynamic program; and often subtle insights are necessary to restructure the formulation so that it can be solved effectively.

We should always start with a brute-force recursive solution, which is the best way to start solving any DP problem! Once we have a recursive solution then we will apply memoization and tabulation techniques.

More so than the optimization technique, DP provides a general framework for analyzing many problems:

  • Longest Common Subsequence
  • Shortest Common Supersequence
  • Longest Increasing Subsequence
  • The Levenshtein distance (Edit distance)
  • Matrix Chain Multiplication
  • 0–1 Knapsack
  • Partition
  • Rod Cutting
  • Coin change-making
  • Word Break

DP is almost used everywhere which requires guaranteed optimal solution. It is heavily used in routing, graph problems, computer vision, computer networks, AI, machine learning etc.