What is dynamic programming?

Dynamic programming (DP) problems exhibit two characteristics:

• Optimal substructure: an optimal solution for the problem can be constructed from the optimal solutions of its subproblems.
• Overlapping subproblems: the problem can be broken down into subproblems which share identical subproblems

Good reads

• HCI NOI 2017 training slides
• Cornell CS5199 2019 slides
• Dynamic programming on WIkipedia

Practice problems

• gecko (NOI 2008) or Unique Paths
• coinbag (essentially the 0-1 knapsack problem)
• knapsack (NOI 2018 Prelims)
• stepgame (similar to the maximum subarray problem)
• Leetcode (tagged dynamic programming)

Well-known DP problems

• Knapsack problem (commonly 0-1 knapsack, meaning only 1 of each item max)
• Fibonacci number