DynamicProgramming - GitLite

KO | EN

gitlite — search

#javascript #python #hacktoberfest #go #machine-learning #rust #docker #macos #kubernetes #security #pytorch #ios #openai #open-source

DynamicProgramming

(★ 157)

DP vs Recursion Code

File Explorer

Download Latest Version (.zip)

0005_longestPalindrome_DP.py
0005_longestPalindrome_Recursion.py
0022_GenerateParentheses_DP.py
0022_GenerateParentheses_Recursion.py.py
0045_JumpGameII_DP.py
0045_JumpGameII_Recursion.py
0053_MaximumSubarray_DP.py
0053_MaximumSubarray_Recursion.py
0070_Climb Stairs_DP.py
0070_Climb Stairs_Recursion.py
0070_Climb Stairs_Time Complexity.py
0072_EditDistance_DP.py
0072_EditDistance_Recursion.py
0091_DecodeWays_DP.py
0091_DecodeWays_Recursion.py
0097_InterleavingString_DP.py
0097_InterleavingString_Recursion.py
0118_PascalsTriangle_DP.py
0118_PascalsTriangle_Recursion.py
0119_PascalsTriangleII_DP.py
0119_PascalsTriangleII_Recursion.py
0121_BestTimeToBuyAndSellStock.py
0121_BestTimeToBuyAndSellStock_Recursion.py
0338_CountingBits_DP.py
0338_CountingBits_Recursion.py
0392_IsSubsequence.py
0392_IsSubsequence_Recursion.py
0509_Fibonacci Number_DP.py
0509_Fibonacci Number_Recursion.py
1025_DivisorGame_DP.py
1025_DivisorGame_Recursion.py
README.md

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

# Dynamic Programming Repository: Classic Problems Solved 🚀

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.

## Table of Contents 📚
- [About the Repository](#about-the-repository)
- [Installation](#installation)
- [Problems Solved](#problems-solved)
  - [All Problems](#all-problems)
  - [Fibonacci Sequence](#fibonacci-sequence)
  - [Climbing Stairs](#climbing-stairs)
- [Usage](#usage)
- [Contributing](#contributing)
- [License](#license)
- [Contact](#contact)
- [Acknowledgments](#acknowledgments)

## About the Repository

This repository includes Python scripts that demonstrate dynamic programming and recursion solutions to well-known problems, currently featuring:
- Fibonacci Sequence (Leetcode 509)
   - [Recursion vs. Dynamic Programming: Climbing Stairs](https://medium.com/geekculture/recursion-vs-dynamic-programming-climbing-stairs-48032b31db98)
- Climbing Stairs (Leetcode 70)
   - [Recursion vs. Dynamic Programming: Climbing Stairs](https://medium.com/geekculture/recursion-vs-dynamic-programming-climbing-stairs-48032b31db98)

Each solution is discussed with respect to both its recursive and dynamic programming implementations, including analysis of time and space complexities.

## Installation 💽

To clone and run these scripts locally, use the following commands:

```bash
git clone https://github.com/yourusername/dynamic-programming-problems.git
cd dynamic-programming-problems
```

## Problems Solved

### All 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)

### Fibonacci Sequence 🧬

**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**:

```bash
python fibonacci.py 10
```

**Detailed Analysis**: Includes performance comparison of recursive vs dynamic programming approaches with visual aids.

### Climbing Stairs 🧗‍♂️

**Description**: Determine the number of ways to climb `n` steps when you can climb either one or two steps at a time.

**Example Usage**:

```bash
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.

## Usage 🚀

To run any script, navigate to the specific problem directory and run the Python script with an appropriate argument. For example:

```bash
python fibonacci.py 10
```

Replace `10` with any number to compute its Fibonacci value using dynamic programming.

## Contributing 🤝

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.

## License 📄

This project is licensed under the MIT License - see the [LICENSE.md](LICENSE.md) file for details.

## Contact 📧

If you have any questions or suggestions, please contact me via [GitHub email](mailto:markusma@alumni.upenn.edu).

## Acknowledgments 🎉

Special thanks to:
- [Towards Data Science](https://towardsdatascience.com/) and [Geek Culture](https://medium.com/geekculture) for hosting the articles that inspired these solutions.
- Contributors and readers who provide valuable feedback and suggestions.