| 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$?|

|[0-1 Knapsack](../dynamic_programming/knapsack.md)| 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 (LIS)| You are given an array containing $N$ integers. Your task is to determine the LIS in the array, i.e., a subsequence where every element is larger than the previous one.|

|[Longest Increasing Subsequence (LIS)](../dynamic_programming/longest_increasing_subsequence.md)| You are given an array containing $N$ integers. Your task is to determine the LIS in the array, i.e., a subsequence where every element is larger than the previous one.|

| Counting Paths in a 2D Array| 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).|

| 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"]|

* Bitmask Dynamic Programming

*[Bitmask Dynamic Programming](../dynamic_programming/profile-dynamics.md)

* Digit Dynamic Programming

* Dynamic Programming on Trees

Here, by the minimum enclosing circle (MEC) we mean a circle with minimum possible radius that contains all the $n$p, inside the circle or on its boundary. This problem has a simple randomized solution that, on first glance, looks like it would run in $O(n^3)$, but actually works in $O(n)$ expected time.

Here, by the minimum enclosing circle (MEC) we mean a circle with minimum possible radius that contains all the $n$points, inside the circle or on its boundary. This problem has a simple randomized solution that, on first glance, looks like it would run in $O(n^3)$, but actually works in $O(n)$ expected time.

To better understand the reasoning below, we should immediately note that the solution to the problem is unique:

??? question "Why is the MEC unique?"

[SGU253 Theodore Roosevelt](https://codeforces.com/problemsets/acmsguru/problem/99999/253)

[Codeforces 55E Very simple problem](https://codeforces.com/contest/55/problem/E)

*[SGU253 Theodore Roosevelt](https://codeforces.com/problemsets/acmsguru/problem/99999/253)

*[Codeforces 55E Very simple problem](https://codeforces.com/contest/55/problem/E)

*[Codeforces 166B Polygons](https://codeforces.com/problemset/problem/166/B)

Now we have to learn to check this fact for each vertex efficiently. We'll use "time of entry into node" computed by the depth first search.

So, let $\mathtt{tin}[v]$ denote entry time for node $v$. We introduce an array $\mathtt{low}$ which will let us store thenode withearliest entry time found in the DFS search that a node $v$ can reach with a single edge from itself or its descendants. $\mathtt{low}[v]$ is the minimum of $\mathtt{tin}[v]$, the entry times $\mathtt{tin}[p]$ for each node $p$ that is connected to node $v$ via a back-edge $(v, p)$ and the values of $\mathtt{low}[to]$ for each vertex $to$ which is a direct descendant of $v$ in the DFS tree:

So, let $\mathtt{tin}[v]$ denote entry time for node $v$. We introduce an array $\mathtt{low}$ which will let us store the earliest entry time of the node found in the DFS search that a node $v$ can reach with a single edge from itself or its descendants. $\mathtt{low}[v]$ is the minimum of $\mathtt{tin}[v]$, the entry times $\mathtt{tin}[p]$ for each node $p$ that is connected to node $v$ via a back-edge $(v, p)$ and the values of $\mathtt{low}[to]$ for each vertex $to$ which is a direct descendant of $v$ in the DFS tree:

$$\mathtt{low}[v] = \min \left\{

- Dynamic Programming

-[Introduction to Dynamic Programming](dynamic_programming/intro-to-dp.md)

-[Knapsack Problem](dynamic_programming/knapsack.md)

-[Longest increasing subsequence](dynamic_programming/longest_increasing_subsequence.md)

- DP optimizations

-[Divide and Conquer DP](dynamic_programming/divide-and-conquer-dp.md)

-[Knuth's Optimization](dynamic_programming/knuth-optimization.md)

- Miscellaneous

- Sequences

-[RMQ task (Range Minimum Query - the smallest element in an interval)](sequences/rmq.md)

-[Longest increasing subsequence](sequences/longest_increasing_subsequence.md)

-[Search the subsegment with the maximum/minimum sum](others/maximum_average_segment.md)

-[K-th order statistic in O(N)](sequences/k-th.md)

-[MEX task (Minimal Excluded element in an array)](sequences/mex.md)