Inspired by Tutorial Non-trivial DP Tricks and Techniques, by zscoder, This is actually a well known DP trick, and has appeared in some problems, but I have not found a detailed tutorial to easily understand it from scratch, me and some friends had troubles to learn this trick, so I will try to explain in a simple and detailed way.
The simplest problem that can be solved with this:
Given a number $$$n$$$, count the number of permutations of length $$$n$$$.
Yes, you read it well, we are going to compute $$$n!$$$ with a complicated dynamic programming in $$$O(n^2)$$$, isn't that amazing? (Do not be afraid, with this trick you will solve problems that can not be solved with basic combinatorics)
Basic Insights:
We will try to build all the permutations.
We will insert the numbers from $$$1$$$ to $$$n$$$ in increasing order, when we insert the number $$$i+1$$$, we will have some chunks or connected components of the permutation that will contain all numbers from $$$1$$$ to $$$i$$$, let's focus on this $$$i$$$-th stage:
For example if we are going to insert $$$4$$$, and we are counting the permutations of size $$$7$$$, we can have two components, like $$$(2)$$$ and $$$(3, 1)$$$, that means that the final permutation will look like $$$(2??31??)$$$ or $$$(?2?31??)$$$, that is, there will be some numbers between each component (greater than $$$i$$$, because all others are already placed), that will be placed in some later operation, the components will appear in order, and the adjacent numbers in the components will be adjacent in the final permutation.
In the final permutation there will be some numbers from $$$i$$$ to $$$n$$$ (maybe $$$0$$$), then the first component, then other numbers greater than $$$i$$$ (at least one, since otherwise the first and the second component would be only one bigger component), the second component, and so on, finally after the last component there may be some numbers greater than $$$i$$$. Note that the components should appear in order.
States:
Now, let $$$DP_{i, j}$$$ be the number of ordered sets of components formed by the numbers from $$$1$$$ to $$$i$$$, with $$$j$$$ components, for example if we are counting the permutations of size $$$7$$$ and we have two components, $$$(2)$$$ and $$$(3, 1)$$$, their ordered set is $$$( (2) , (3, 1) )$$$ and will be counted in $$$DP_{3, 2}$$$.
Here in an ordered set, the order of elements matters, not just their values, set $$$(a, b)$$$ $$$\neq$$$ set $$$(b, a)$$$, and set $$$(a, b)$$$ $$$\neq$$$ set $$$(a, c)$$$.
The final answer of the problem will be $$$DP_{n, 1}$$$, since that will store the number of single components of size $$$n$$$, that is, the number of permutations of size $$$n$$$.
Transitions:
Now, for the transitions think how inserting the $$$i+1$$$-th number will affect the set of components formed by numbers from $$$1$$$ to $$$i$$$:
We can create a new component that will contain only number $$$i+1$$$, we can place this new components in any place between two already existing components, before the first one, or after the last one. This transition will be $$$DP_{i+1, j+1} += DP_{i, j} \cdot (j + 1)$$$ since we will end up with one new component, and we will have $$$j+1$$$ available places.
We can add the number $$$(i+1)$$$ at the beginning or the end of any existing component, let's say, we have this set of components $$$( (1, 2), (4), (3, 5) )$$$, we can place the $$$6$$$ at the beginning or the end of any component, if we put at the beginning of the first one, we will end up with $$$( (6, 1, 2), (4), (3, 5) )$$$. This transition will be $$$DP_{i+1, j} += DP_{i, j} \cdot (2 \cdot j)$$$, since we will end up with the same number of components, and we will have $$$(2 \cdot j)$$$ available places for $$$i+1$$$.
We can merge two components into a bigger one placing $$$i+1$$$ at the end of a component and at the beginning of the next one at the same time, let's say, we have this set of components $$$( (1, 2), (4), (3, 5) )$$$, we can merge the first and the second components with $$$6$$$, which will lead to $$$( (1, 2, 6, 4), (3, 5) )$$$. This transition will be $$$DP_{i+1, j-1} += DP_{i, j} \cdot (j - 1)$$$, since we will end up with one less component (we merged two into one), and we can merge any two consecutive components, so there are $$$(j - 1)$$$ choices.
Complexity
There are $$$O(n^2)$$$ states, and $$$O(1)$$$ transitions per state, each one can be done in $$$O(1)$$$ time complexity, also we can get rid of storing all states in memory only storing the current and the previous one, so the total time complexity is $$$O(n^2)$$$ and the memory usage is $$$O(n)$$$ or $$$O(n^2)$$$ depending on the implementation.
Proof of correctness:
First, we will prove that any permutation can be counted with this dp, and after that, that each one will be counted exactly once.
First, let's show by induction that the subset of the first $$$i$$$ elements of any permutation is always an ordered set of components, it will be obviously true at $$$i = 0$$$, since it's just the empty set. Now, for each $$$i$$$, we claim that we have the ordered set of the first $$$i-1$$$ elements, let's find $$$i$$$ in the permutation:
If $$$p_i < p_{i-1}$$$ and $$$p_i < p_{i+1}$$$, then we can add a new component with the element $$$i$$$ between the component that ends with the previous ocurrence of a number smaller than $$$i$$$, and the components that starts with the next ocurrence of a number smaller than $$$i$$$ in the permutation, also this component may be the first one if there is no previous ocurrence of a number smaller than $$$i$$$, or the last one if there is no such next ocurrence.
If $$$p_i > p_{i-1}$$$ and $$$p_i < p_{i+1}$$$, then we can add $$$i$$$ at the end of the component that ends at $$$i-1$$$.
If $$$p_i < p_{i-1}$$$ and $$$p_i > p_{i+1}$$$, then we can add $$$i$$$ at the beginning of the component that starts at $$$i+1$$$.
If $$$p_i > p_{i-1}$$$ and $$$p_i > p_{i+1}$$$, then we can merge the component that ends at $$$i-1$$$ with the one that starts at $$$i+1$$$ by placing $$$i$$$ between them.
So for any case we can obtain a new ordered set from the previous one by adding $$$i$$$.
This way we have proven that each subset that contains the smallest $$$i$$$ numbers of a permutation of size $$$n$$$ corresponds to a ordered set of components, and, since for a fixed permutation, in each stage we will only have exactly one option that can end up in that permutation after all stages are done, each permutation will be counted exactly once.
Problems that can be solved with this trick:
Building the permutations in this way can be used to count the number of permutations with some properties, Now I will share some problems that can be solved with this trick, in relative increasing order of dificulty:
Count the number of permutations of length $$$n$$$, that don't have three consecutive elements increasing or decreasing, that is, there is no $$$i$$$ $$$(1 \leq i \leq n-2)$$$ such that $$$p_i > p_{i+1}$$$ and $$$p_{i+1} > p_{i+2}$$$, or $$$p_i < p_{i+1}$$$ and $$$p_{i+1} < p_{i+2}$$$, starts with a number $$$s$$$ and ends with a number $$$e$$$. This problem is actually CEOI 2016 Kangaroo. You can see the solution explained here.
E. Phoenix and Computers , editorial doesn't mention that can be solved with this, but you can see a code with comments here.
JOI 2016 Open Contest — Skyscrapers, Given $$$a_1, a_2, ..., a_n$$$ find the number of permutations of these numbers such that $$$|a_1 - a_2| + |a_2 - a_3| + ... + |a_{n - 1} - a_n| ≤ L$$$ where $$$L$$$ is a given integer. Constraints : $$$n ≤ 100, L ≤ 1000, a_i ≤ 1000$$$. You can see the solution explained here in "Connected Component" DP section.
UTS Open '21 P7 — April Fools, editorial notes can be found here
I would be grateful if you discuss about the topic in comments, let me know if there is any mistake in the blog, or share other problems that can be solved with this trick.
