Dynamic Programming is a problem-solving technique for solving a problem by breaking it into similar subproblems, solving each of those subproblems just once, and storing their solutions using a memory-based data structure. Each of the subproblem solutions is indexed in some way, typically based on the values of its input parameters, so as to facilitate its lookup. So the next time the same subproblem occurs, instead of recomputing its solution, one simply looks up the previously computed solution, thereby saving computation time. This technique of storing solutions to subproblems instead of recomputing them is called memoization.
There are two key attributes that a problem must have in order for dynamic programming to be applicable: optimal substructure and overlapping sub-problems. If a problem can be solved by combining optimal solutions to non-overlapping sub-problems, the strategy is called divide and conquer instead. This is why merge sort and quick sort are not classified as dynamic programming problems.
This repository contains some famous Problems that can be solved by Dynamic Programming. Any Contributions about Problems and Solutions in any Programming Languages are welcome.
You can send a new Pull Request about:
- Contributing a new Problem that can be solved by Dynamic Programming
- Create a new Folder for it. The folder name must be the name of the Problem
- Inside the folder, create a file named
problem.md, and write the content of the Problem here
- Contributing a Solution for a Problem which is written by Dynamic Programming
- Your file must be put inside the correct folder that the Solution belongs to
- Your file must be named as
solution. For example:solution.py,solution.cpp,solution.php...
- Re-implement an existing Solution in anothor Programming Language
- Improve the Solution, or add more Comments into it