Welcome to my dynamic programming repository where I explore and explain solutions to classic problems using both recursion and dynamic programming techniques. This repository serves as a practical reference for coding enthusiasts interested in understanding and applying dynamic programming strategies to solve problems efficiently.
- About the Repository
- Installation
- Problems Solved
- Usage
- Contributing
- License
- Contact
- Acknowledgments
This repository includes Python scripts that demonstrate dynamic programming and recursion solutions to well-known problems, currently featuring:
- Fibonacci Sequence (Leetcode 509)
- Climbing Stairs (Leetcode 70)
Each solution is discussed with respect to both its recursive and dynamic programming implementations, including analysis of time and space complexities.
To clone and run these scripts locally, use the following commands:
git clone https://github.com/yourusername/dynamic-programming-problems.git
cd dynamic-programming-problems
- Longest Palindromic Substring (Leetcode 5)
- Generate Parentheses (Leetcode 22)
- Jump Game II (Leetcode 45)
- Maximum Subarray (Leetcode 53)
- Edit Distance (Leetcode 72)
- Decode Ways (Leetcode 91)
- Interleaving String (Leetcode 97)
- Pascal's Triangle (Leetcode 118)
- Pascal's Triangle II (Leetcode 119)
- Best Time to Buy and Sell Stock (Leetcode 121)
- Counting Bits (Leetcode 338)
- Is Subsequence (Leetcode 392)
- Divisor Game (Leetcode 1025)
Description: The Fibonacci sequence is a series of numbers where a number is the sum of the two preceding ones, usually starting with 0 and 1.
Example Usage:
python fibonacci.py 10
Detailed Analysis: Includes performance comparison of recursive vs dynamic programming approaches with visual aids.
Description: Determine the number of ways to climb n
steps when you can climb either one or two steps at a time.
Example Usage:
python climbing_stairs.py 5
Detailed Analysis: Focuses on optimizing the recursive solution using dynamic programming techniques to reduce time complexity from exponential to polynomial.
To run any script, navigate to the specific problem directory and run the Python script with an appropriate argument. For example:
python fibonacci.py 10
Replace 10
with any number to compute its Fibonacci value using dynamic programming.
Contributions to improve the existing solutions or add new problem solutions are welcome. Please fork the repository, make your changes, and submit a pull request.
This project is licensed under the MIT License - see the LICENSE.md file for details.
If you have any questions or suggestions, please contact me via GitHub email.
Special thanks to:
- Towards Data Science and Geek Culture for hosting the articles that inspired these solutions.
- Contributors and readers who provide valuable feedback and suggestions.