PSolving Paradigms

An educational repository of common problems and their solutions in dynamic programming methods and techniques, including prerequisites (approaches of greedy, brute-force (iterative, recursive and state-space search) and binary search), for competitive programmers. Also, I attached a sheet of problems from several online judges (basic problems and extra) in details; difficulty, topics, hints and notes, in case you needed to solve.

I tried my best to make my code clean and readable. Also, I made comments for unclear statements, as possible. I wish this will be helpful! Thank you!

Content:

1. Brute Force

• 1.1 Iterative Brute Force
• 1.2 Recursive Brute Force (Backtracking)
• 1.3 State-Space Search

2. Greedy

3. Binary Search

4. Dynamic Programming

• 4.01 Max 1D Range Sum
• 4.02 Max 2D Range Sum
• 4.03 Longest Increasing Subsequence (LIS)
• 4.04 Knapsack
• 4.05 Coin Change
• 4.06 Probabilities
• 4.07 Bitmasks
• 4.08 Digits
• 4.09 Grids and Paths
• 4.10 Traveling Salesman Problem (TSP)
• 4.11 Bitonic TSP
• 4.12 Strings
• 4.13 Tiling (Counting)
• 4.14 DP involving graphs
• 4.15 DP speed-up with matrix power
• 4.16 DP speed-up with convex hull
• 4.17 DP speed-up with Divide and Conquer Optimization
• 4.18 DP speed-up with Knuth Optimization
• 4.19 DP speed-up with Data Structures
• 4.20 Building Up
• 4.21 Non Classical

5. Other Techniques