Knuth's Optimization

Introduction

Knuth's optimization is a special case of Range DP. In general, it is used to solve DP problems with transitions of the form

Further, the cost function must satisfy the following conditions for all $a\leq b\leq c \leq d$:

1. $\texttt{cost}[b][c] \leq \texttt{cost}[a][d]$
2. $\texttt{cost}[a][c] + \texttt{cost}[b][d] \leq \texttt{cost}[a][d] + \texttt{cost}[b][c]$ (the quadrangle inequality)

Define $\texttt{opt}[i][j]$ be the index for which $\texttt{dp}[i][k] + \texttt{dp}[k+1][j]$ takes on its minimum value, or equivalently,

If more than one such index exists, then take the minimum (or the maximum, doesn't matter). Then, assuming conditions on the dp transition and the cost function to be satisfied, we can show that $\texttt{opt}$ satisfies

The proof of correctness for this claim is in the resources above.

The structure of the code is identical to that of Range DP, with the exception of maintaining the $\texttt{opt}$ array. To calculate $\texttt{dp}[i][j]$ and $\texttt{opt}[i][j]$, it is only necessary to check values of $k$ between $\texttt{opt}[i][j-1]$ and $\texttt{opt}[i+1][j]$. Because of the monotonicity of $\texttt{opt}$, the time complexity of the final algorithm can be shown to be $\mathcal{O}(N^2)$.

Problems

Connected-Component DP

Introduction

Let's define a "connected component" as an array of elements with a specific order. We will surround these with brackets. For example, $[1, 6]$ and $[2, 3, 5]$ are connected components.

Let's define a "collection" of connected components as several non-adjacent connected components without any order. We will surround these with braces. For example, $\{[1,6],[2,3,5],[7],[4,8,9]\}$ is a collection of 4 connected components. $\{[7],[1,6],[4,8,9],[2,3,5]\}$ is another representation of the same collection.

In connected component DP, we can use these components to create a structure given some requirements. This often appears with permutation-related problems.

Connected component DP involves the state $\texttt{dp}[i][j]$ as some quantity with the first $i$ elements arranged in $j$ connected components. There are three main transitions when adding a new element to the collection.

1. Add it as a new component. Number of components increases. $\texttt{dp}[i][j] \gets \texttt{dp}[i-1][j-1]$
2. Add it onto the end of an existing component. Number of components remains same. $\texttt{dp}[i][j] \gets \texttt{dp}[i-1][j]$
3. Add it in between two components to merge them. Number of components decreases. $\texttt{dp}[i][j] \gets \texttt{dp}[i-1][j+1]$

The quantity for a complete array is $\texttt{dp}[n][1]$, or the quantity after arranging of all $n$ elements into $1$ component.

Solution - Counting Permutations II

Time Complexity: $\mathcal{O}(n^2)$

This problem requires us to store additional information. Define $\texttt{dp}[i][j][k]$ as the number of valid configurations of the numbers from $1$ to $i$ into $j$ connected components, where value $i$ has $k$ borders where a border is a side lacking a neighbor. For instance, the collection $\{[1,6],[2,3,5],[7],[4,8,9]\}$ would be counted in the state $\texttt{dp}[9][4][1]$.

1. If $i$ has no borders, then $i$ must point two existing connected components.
2. If $i$ has one border, then $i$ must be appended on to an existing connected component.
3. If $i$ has two borders, it must be inserted as its own connected component.

This corresponds to the following transitions:

The base case is $\texttt{dp}[0][0][0]=1$, and the final answer is $\sum_k \texttt{dp}[n][1][k]$.

Copy
#include <bits/stdc++.h>

const int MOD = 1000000007;

int main() {
	int N;
	std::cin >> N;
	std::vector dp(N + 1, std::vector<std::array<long long, 3>>(N + 2));
	for (auto &a : dp)
		for (auto &b : a) b.fill(0);

Problems