Dynamic Programming

Dynamic programming is a technique that combines the correctness of complete search and the efficiency of greedy algorithms.

Dynamic Programming is “Smart Brute-Forcing”.

There are two uses for dynamic programming:

  • Finding an optimal solution: We want to find a solution that is as large as possible or as small as possible.
  • Counting the number of solutions: We want to calculate the total number of possible solutions.

Dynamic programming can be applied if the problem can be divided into overlapping subproblems that can be solved independently.

Steps

  1. Recursion
    1. Define Subproblems count # subproblems
    2. Guess (part of solution) count # choices
    3. Relate Subproblem Solutions compute time/subproblem
  2. Apply Memoization (top-down DP), or
  3. Apply Tabulation (Iterative / Bottom-Up DP)
  4. Make sure to check Topological Order

Concepts

Simple. most of the Dynamic Programming problems are solved in two ways:  

  1. Tabulation: Bottom Up
  2. Memoization: Top Down

More advanced concepts are explored for Competitive Programming https://codeforces.com/blog/entry/8219

DP on trees: https://codeforces.com/blog/entry/20935

Applications

Other:

Other

Recursive vs. Iterative DP

  1. Errichto says this iterative, bottom-up approach, is preferred in Competitive Programming
  2. The Competitive Programmer’s Handbook also says the same, because it is shorter and has lower constant factors.
  3. However, its often easier to think about DP solutions in terms of Recursive Algorithms