Patterns in Dynamic Programming - 2

Disclaimer: The method described below is not universal, but it can often solve a problem or help you come to the right solution.

If a problem asks you to optimally destroy/collapse/merge (or similar) an array, then you should try to solve it using dynamic programming on subsegments.

Let's get dp[l][r] - the optimal answer for a subsegment with indices from l to r. Recalculation of dynamics is highly task dependent, but there are the following general ideas:

1) Look at the extreme elements l and r. If they match or complement in some other way, then most likely it will be possible to update the value of dp[l][r] via dp[l+1][r-1]. Otherwise via dp[l][r-1] or dp[l+1[r].

2) It often happens that the segment [l;r] cannot be represented through a single construction. Then it is necessary to consider all possible sections of this subsegment into two parts, that is, iterate over the element k from l to r-1 and recalculate dp[l][r] through dp[l][k] and dp[k+1][r] . In smaller subsegments, these sections were also sorted out, therefore, in fact, the options for splitting the subsegment [l;r] not only into two parts, but into any number of them are taken into account.
 

Disclaimer: The method described below is not universal, but it can often solve a problem or help you come to the right solution.

If you need to check the existence of a permutation in a problem, or find the number of permutations that match, or something similar, then you should consider using dynamic subset programming.

The main parameter will be a bitmask, which will show which elements have already been included in the permutation, and which are not. Also often required is a second parameter that indicates which element was included last.

Often permutations can be seen in the context of paths in graphs. Accordingly, let us consider a classical example - the Hamiltonian path problem.
A Hamiltonian path is a simple path that passes through each vertex of the graph exactly once. It can be represented simply as a permutation of length n, where n is the number of vertices. The order within this permutation will indicate the order in which the vertices in this path are traversed.

In order to check the presence of a Hamiltonian path in the graph, let's start the dynamics dp[mask][last] - is there a simple path that bypassed the vertices marked with ones in the mask bitmask and ended up at the last vertex.
The initial values ​​will be dp[2ⁱ][i] = true, the rest false, which means that there is always an empty path starting at any of the vertices.
Having the value true in dp[mask][last] we will make transitions forward, in the sense of "extending the path". That is, we will look for the numbers of vertices that are marked with zero in the mask (we have not yet visited them on the way) and at the same time such that there is an edge from last to this vertex (the path must be extended by an existing edge). That is, we do dp[mask | 2^k][k] = true if dp[mask][last] = true AND mask & 2^k = 0 (vertex k has not yet been visited) And there is an edge last -> k.
Ultimately, a Hamiltonian path exists if there is a true value in dp for the parameters of the all-ones bitmask and any last vertex.