Skip to content

Added Descriptions to Classic DP Problems #1269

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 6 commits into from
Jun 9, 2024
Merged

Added Descriptions to Classic DP Problems #1269

Changes from all commits
Commits
Show all changes
6 commits
Select commit Hold shift + click to select a range
884eb1e
Update intro-to-dp.md
Zyad-Ayad Apr 24, 2024
6c693ed
Update intro-to-dp.md
Zyad-Ayad Apr 24, 2024
762f076
Update intro-to-dp.md
Zyad-Ayad Apr 24, 2024
fa03985
Update intro-to-dp.md
Zyad-Ayad Apr 24, 2024
3572863
Update intro-to-dp.md
Zyad-Ayad Apr 25, 2024
ff4b380
Touch for CI
adamant-pwn Jun 9, 2024
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
33 changes: 20 additions & 13 deletions src/dynamic_programming/intro-to-dp.md
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -130,19 +130,22 @@ That's it. That's the basics of dynamic programming: Don't repeat work you've do
One of the tricks to getting better at dynamic programming is to study some of the classic examples.

## Classic Dynamic Programming Problems
- 0-1 Knapsack
- Subset Sum
- Longest Increasing Subsequence
- Counting all possible paths from top left to bottom right corner of a matrix
- Longest Common Subsequence
- Longest Path in a Directed Acyclic Graph (DAG)
- Coin Change
- Longest Palindromic Subsequence
- Rod Cutting
- Edit Distance
- Bitmask Dynamic Programming
- Digit Dynamic Programming
- Dynamic Programming on Trees
| Name | Description/Example |
| ---------------------------------------------- | -------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| 0-1 knapsack | Given $W$, $N$, and $N$ items with weights $w_i$ and values $v_i$, what is the maximum $\sum_{i=1}^{k} v_i$ for each subset of items of size $k$ ($1 \le k \le N$) while ensuring $\sum_{i=1}^{k} w_i \le W$? |
| Subset Sum | Given $N$ integers and $T$, determine whether there exists a subset of the given set whose elements sum up to the $T$. |
| Longest Increasing Subsequence | You are given an array containing $N$ integers. Your task is to determine the LCS in the array, i.e., LCS where every element is larger than the previous one. |
| Counting all possible paths in a matrix. | Given $N$ and $M$, count all possible distinct paths from $(1,1)$ to $(N, M)$, where each step is either from $(i,j)$ to $(i+1,j)$ or $(i,j+1)$. |
| Longest Common Subsequence | You are given strings $s$ and $t$. Find the length of the longest string that is a subsequence of both $s$ and $t$. |
| Longest Path in a Directed Acyclic Graph (DAG) | Finding the longest path in Directed Acyclic Graph (DAG). |
| Longest Palindromic Subsequence | Finding the Longest Palindromic Subsequence (LPS) of a given string. |
| Rod Cutting | Given a rod of length $n$ units, Given an integer array cuts where cuts[i] denotes a position you should perform a cut at. The cost of one cut is the length of the rod to be cut. What is the minimum total cost of the cuts. |
| Edit Distance | The edit distance between two strings is the minimum number of operations required to transform one string into the other. Operations are ["Add", "Remove", "Replace"] |

## Related Topics
* Bitmask Dynamic Programming
* Digit Dynamic Programming
* Dynamic Programming on Trees

Of course, the most important trick is to practice.

Expand All @@ -151,3 +154,7 @@ Of course, the most important trick is to practice.
* [LeetCode - 118. Pascal's Triangle](https://leetcode.com/problems/pascals-triangle/description/)
* [LeetCode - 1025. Divisor Game](https://leetcode.com/problems/divisor-game/description/)

## Dp Contests
* [Atcoder - Educational DP Contest](https://atcoder.jp/contests/dp/tasks)
* [CSES - Dynamic Programming](https://cses.fi/problemset/list/)

Loading