Dynamic Programming

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)

Types of Dynamic Programming Tools

• Tabulation
• Memoization
• Sliding Window