Skip to content

rabiulcste/dynamic-programming

BranchesTags

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

63 Commits
0-1 Knapsack (Bottom Up).cpp
0-1 Knapsack (Bottom Up).cpp
 
 
0-1 Knapsack.cpp
0-1 Knapsack.cpp
 
 
Bitmask Dp.cpp
Bitmask Dp.cpp
 
 
Building Bridges Problem.cpp
Building Bridges Problem.cpp
 
 
Coin Change (optimized).cpp
Coin Change (optimized).cpp
 
 
Coin Change.cpp
Coin Change.cpp
 
 
Digit DP.cpp
Digit DP.cpp
 
 
Distinct Subsequence.cpp
Distinct Subsequence.cpp
 
 
Edit Distance Bottom Up.cpp
Edit Distance Bottom Up.cpp
 
 
Edit Distance Recursive.cpp
Edit Distance Recursive.cpp
 
 
Josephus Problem.cpp
Josephus Problem.cpp
 
 
LCS Length (bottom up).cpp
LCS Length (bottom up).cpp
 
 
LCS Print (sentence).cpp
LCS Print (sentence).cpp
 
 
LCS Print Backtrack.cpp
LCS Print Backtrack.cpp
 
 
LIS O(nlogn).cpp
LIS O(nlogn).cpp
 
 
Length Of LIS.cpp
Length Of LIS.cpp
 
 
Longest Common Subsequence.cpp
Longest Common Subsequence.cpp
 
 
Longest Increasing Subsequence.cpp
Longest Increasing Subsequence.cpp
 
 
Longest Palindromic Subsequence.cpp
Longest Palindromic Subsequence.cpp
 
 
Matrix Chain Multiflication.cpp
Matrix Chain Multiflication.cpp
 
 
Max 1D Range Sum.cpp
Max 1D Range Sum.cpp
 
 
MaxSumForNonAdjacentElements.cpp
MaxSumForNonAdjacentElements.cpp
 
 
Min Vertex Cover.cpp
Min Vertex Cover.cpp
 
 
Minimum Cost Path Problem.cpp
Minimum Cost Path Problem.cpp
 
 
Minimum number of Coins to make Change bruteforce.cpp
Minimum number of Coins to make Change bruteforce.cpp
 
 
Minimum number of coins for a given change.cpp
Minimum number of coins for a given change.cpp
 
 
Palindrome Partitioning Min Cut.cpp
Palindrome Partitioning Min Cut.cpp
 
 
Palindrome Partitioning.cpp
Palindrome Partitioning.cpp
 
 
README.md
README.md
 
 
Range Min Query (Sparse Table).cpp
Range Min Query (Sparse Table).cpp
 
 
Shortest Common Subsequence.cpp
Shortest Common Subsequence.cpp
 
 
Sum of Digits.cpp
Sum of Digits.cpp
 
 
Sum of subset (2D).cpp
Sum of subset (2D).cpp
 
 
Weighted Job Scheduling.cpp
Weighted Job Scheduling.cpp
 
 
_config.yml
_config.yml
 
 
nCr.cpp
nCr.cpp
 
 
stockSellwith2Transactions.cpp
stockSellwith2Transactions.cpp
 
 

Repository files navigation

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

About

Classical dynamic programming problems solution and algorithms

rabiul.me/dynamic-programming/

Topics

competitive-programming dynamic-programming

Resources

Readme
Activity

Stars

29 stars

Watchers

3 watching

Forks

15 forks
Report repository

Releases

No releases published

Packages

No packages published

Contributors 2

  •  
  •  

Languages