Dynamic Programming

This is a very general approach to solving problems.

Identification

• Typically, all the problems that require maximizing or minimizing certain quantities or counting problems that say to count the arrangements under certain conditions or certain probability problems can be solved by using Dynamic Programming.
• All dynamic programming problems satisfy the overlapping subproblems property and most of the classic Dynamic programming problems also satisfy the optimal substructure property. Once we observe these properties in a given problem be sure that it can be solved using Dynamic Programming.

Steps to Solve

1. Determine choices
2. Determine sub-problem
   1. in 1D, this is a single state
   2. in 2D, state is defined by 2 independent variables

Important

A choice is not a state! It is an action!

1D DP

• Usually spans across an array

2D DP

• Matrix type questions where we search a grid

Determining the Subproblem

This is the key to DP.

• Has to do with the index / state that we are caching ex. What is the longest path we can make starting at (i, j)?

Types of Dynamic Programming Programs

• Max or min
  • This is where you use max(firstRun, secondRun) and don’t call 1+ on your dp call
• Counting length
  • This is where you hit a 1 + dp(i, j)
• Finding the shortest path of DAGs
• Leetcode - Longest Increasing Subsequence
• Edit Distance
• Knapsack
• All-Pairs Shortest Paths

Time Complexity

In general, time complexity of a DP solution should be O(num states * work per state) where work per state is usually O(1) and num states is typically rows*cols for a grid exploration.

Types of Dynamic Programming Tools

• Tabulation
• Memoization
• Sliding Window

DAG

Note that every dynamic programming algorithm has an underlying DAG that links the subproblems. This is the best way of visualizing this (well I guess I do it as a tree). Once you determine what the vertices are and the weight of the edges, we typically just need to find some sort of path from our starting vertex to our end vertex (minimum path usually).

Example from edit distance