13-dynamic-programming-i

Unit 13: Dynamic Programming I

This unit covers the two Dynamic Programming approaches, namely Top-Down (memoization) and Bottom-Up, as well as three classical problems:

• Partition Problem
• Knapsack
• SSSP on acyclic graphs

Complementary notes can be found in section 3.5 of the book Competitive Programming 3.

Prerequisites

• Unit 1: Complexity
• Unit 2: Linear data structures
• Unit 6: Graph representation
• Unit 10: Recursive backtracking
• Unit 14: Graph traversal (esp. toposort)
• (optional) Unit 17: Single-source shortest path

Practice problems

Easy

• UVa 674 - Coin Change
• UVa 10130 - SuperSale
• UVa 562 - Dividing coins
• UVa 624 - CD
• UVa 103 - Stacking Boxes

Less easy

• UVa 990 - Diving for gold
• UVa 10261 - Ferry Loading
• Codeforces 682D - Alyona and Strings
• UVa 108 - Maximum Sum
• UVa 662 - Fast Food

Not easy

• Kattis - Arranging Hat
• UVa 10032 - Tug of War