Dynamic Programming Problems and Algorithms

What you may learn here?

This repository is full of classical graph theory algorithms and problems solution specially focused on competitive programming. Most of the solutions can be used as a template for further variance solution of specific category. Listed algorithms are very naive and common. For detailed explation follow Graph Algorithms book by Shafayet Ashraf.

Language: C++

List of solutions

• 0-1 Knapsack (Bottom Up)
• 0-1 Knapsack
• Bitmask Dp
• Building Bridges Problem / LIS
• Coin Change (optimized)
• Coin Change DP
• Digit DP / Light OJ 1140 - How Many Zeroes?
• Distinct Subsequence / DP
• Edit Distance Bottom Up / Bottom Up DP
• Edit Distance Recursive / Recursive DP
• Josephus Problem / Recursive DP
• LCS Length (bottom up)
• LCS Print (sentence)
• LCS Print Backtrack
• LIS O(nlogn)
• Length Of LIS
• Longest Common Subsequence
• Longest Increasing Subsequence.cpp LIS/DP a year ago
• Longest Palindromic Subsequence.cpp LCS/DP a year ago
• Matrix Chain Multiflication.cpp Create Matrix Chain Multiflication.cpp 2 years ago
• Max 1D Range Sum.cpp
• MaxSumForNonAdjacentElements
• Min Vertex Cover / Graph+DP
• Minimum Cost Path Problem / Bottom Up DP
• Minimum number of Coins to make Change bruteforce / Coin Change DP
• Minimum number of coins for a given change.cpp Coin Change 2 years ago
• Palindrome Partitioning Min Cut.cpp DP 4 months ago
• Palindrome Partitioning / Matrix Chain Multiplication DP
• Range Min Query (Sparse Table)
• Shortest Common Subsequence
• Sum of Digits.cpp SPOJ CPCRC1C - Sum of Digits
• Sum of subset (2D) / Kadane’s Algo
• Weighted Job Scheduling
• nCr