This approach is called top-down, as we can call the function with a query value and the calculation starts going from the top (queried value) down to the bottom (base cases of the recursion), and makes shortcuts via memoization on the way.

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

* Bitmask Dynamic Programming

* Digit Dynamic Programming

* Dynamic Programming on Trees

* [Codeforces - Zuma](https://codeforces.com/problemset/problem/607/b)

* [LeetCode - 221. Maximal Square](https://leetcode.com/problems/maximal-square/description/)

* [LeetCode - 1039. Minimum Score Triangulation of Polygon](https://leetcode.com/problems/minimum-score-triangulation-of-polygon/description/)

* [Atcoder - Educational DP Contest](https://atcoder.jp/contests/dp/tasks)

* [CSES - Dynamic Programming](https://cses.fi/problemset/list/)

For the cases of multiple edges, we need to be careful when ignoring the edge from the parent. To solve this issue, we can add a flag `parent_skipped` which will ensure we only skip the parent once.

```{.cpp file=bridge_searching_offline}

void IS_BRIDGE(int v,int to); // some function to process the found bridge

bool parent_skipped = false;

if (to == p && !parent_skipped) {

parent_skipped = true;

continue;

}

We can classify the edges of a graph, $G$, using the entry and exit time of the end nodes $u$ and $v$ of the edges $(u,v)$.

**Theorem**. Let $G$ be an undirected graph. Then, performing a DFS upon $G$ will classify every encountered edge as either a tree edge or back edge, i.e., forward and cross edges only exist in directed graphs.

Suppose $(u,v)$ is an arbitrary edge of $G$ and without loss of generality, $u$ is visited before $v$, i.e., $\text{entry}[u] < \text{entry}[v]$. Because the DFS only processes edges once, there are only two ways in which we can process the edge $(u,v)$ and thus classify it:

* The first time we explore the edge $(u,v)$ is in the direction from $u$ to $v$. Because $\text{entry}[u] < \text{entry}[v]$, the recursive nature of the DFS means that node $v$ will be fully explored and thus exited before we can "move back up the call stack" to exit node $u$. Thus, node $v$ must be unvisited when the DFS first explores the edge $(u,v)$ from $u$ to $v$ because otherwise the search would have explored $(u,v)$ from $v$ to $u$ before exiting node $v$, as nodes $u$ and $v$ are neighbors. Therefore, edge $(u,v)$ is a tree edge.

* The first time we explore the edge $(u,v)$ is in the direction from $v$ to $u$. Because we discovered node $u$ before discovering node $v$, and we only process edges once, the only way that we could explore the edge $(u,v)$ in the direction from $v$ to $u$ is if there's another path from $u$ to $v$ that does not involve the edge $(u,v)$, thus making $u$ an ancestor of $v$. The edge $(u,v)$ thus completes a cycle as it is going from the descendant, $v$, to the ancestor, $u$, which we have not exited yet. Therefore, edge $(u,v)$ is a back edge.

Since there are only two ways to process the edge $(u,v)$, with the two cases and their resulting classifications outlined above, performing a DFS upon $G$ will therefore classify every encountered edge as either a tree edge or back edge, i.e., forward and cross edges only exist in directed graphs. This completes the proof.

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

#include <algorithm>

#include <cassert>

#include <vector>

#include <set>

using namespace std;

#include "bridge_searching_offline.h"

vector<pair<int,int>> bridges;

void IS_BRIDGE(int v,int to){

bridges.push_back({v, to});

}

void normalize(vector<pair<int,int>> &v){

for(auto &p : v){

if(p.first > p.second)swap(p.first, p.second);

}

sort(v.begin(), v.end());

}

void test_suite(

int _n,

vector<vector<int>> _adj,

vector<pair<int,int> > expected_bridges){

bridges.clear();

n = _n;

adj = _adj;

find_bridges();

normalize(expected_bridges);

normalize(bridges);

assert(bridges == expected_bridges);

}

int main() {

vector<vector<int>> adj;

auto add_edge = [&](int a,int b){

adj[a].push_back(b);

adj[b].push_back(a);

};

{

int n = 5;

adj.resize(n);

add_edge(0, 1);

add_edge(0, 1);

add_edge(2, 3);

add_edge(3, 4);

vector<pair<int,int> > expected_bridges;

expected_bridges.push_back({2,3});

expected_bridges.push_back({3,4});

// note that 0-1 is not a bridge due to duplicate edges!

test_suite(n, adj, expected_bridges);

adj.clear();

}

{

int n = 7;

adj.resize(n);

add_edge(0, 1);

add_edge(1, 2);

add_edge(2, 3);

add_edge(3, 1);

add_edge(3, 4);

add_edge(0, 4);

add_edge(4, 5);

add_edge(1, 6);

vector<pair<int,int> > expected_bridges;

expected_bridges.push_back({4, 5});

expected_bridges.push_back({1, 6});

test_suite(n, adj, expected_bridges);

adj.clear();

}

{

int n = 4;

adj.resize(n);

add_edge(0, 1);

add_edge(0, 1);

add_edge(1, 2);

add_edge(2, 3);

add_edge(2, 3);

vector<pair<int,int> > expected_bridges;

expected_bridges.push_back({1, 2});

test_suite(n, adj, expected_bridges);

adj.clear();

}

}