PrevNext
Rare
 0/15

Additional DP Optimizations and Techniques

Author: Andi Qu

Additional dynamic programming techniques and optimizations like Knuth's optimization.

Knuth's Optimization

Tutorials

Resources
Jeffrey Xiao
GCP
GFG

Good explanation + Proof of correctness

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

dp[i][j]=cost[i][j]+minik<j(dp[i][k]+dp[k+1][j]).\texttt{dp}[i][j] = \texttt{cost}[i][j] + \min_{i\leq k<j}(\texttt{dp}[i][k] + \texttt{dp}[k+1][j]).

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

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

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

opt[i][j]=arg minik<j(dp[i][k]+dp[k+1][j]).\texttt{opt}[i][j] = \argmin_{i\leq k<j}(dp[i][k] + dp[k+1][j]).

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 opt\texttt{opt} satisfies

opt[i][j1]opt[i][j]opt[i+1][j].\texttt{opt}[i][j-1] \leq \texttt{opt}[i][j] \leq \texttt{opt}[i+1][j].

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 opt\texttt{opt} array. To calculate dp[i][j]\texttt{dp}[i][j] and opt[i][j]\texttt{opt}[i][j], it is only necessary to check values of kk between opt[i][j1]\texttt{opt}[i][j-1] and opt[i+1][j]\texttt{opt}[i+1][j]. Because of the momotonicity of opt\texttt{opt}, the time complexity of the final algorithm can be shown to be O(N2)\mathcal{O}(N^2).

Knuth's Optimization Problems

StatusSourceProblem NameDifficultyTags
CFEasy
SPOJNormal
onlinejudge.orgNormal
onlinejudge.orgHard

Connected-Component DP

Resources
CF

Miscellaneous techniques

Connected-Component DP Problems

This section is not complete.

Any help would be appreciated! Just submit a Pull Request on GitHub.

Make Permutations II a focus problem, move analysis to module.

StatusSourceProblem NameDifficultyTags
CSESEasy
CFEasy
CEOINormal
CFNormal
JOINormal
CFNormal

DP on Broken Profile

Broken profile DP is a subset of bitmask DP. Problems falling under this category generally have the following properties:

  1. They're about filling a 2D grid.
  2. One of the dimensions is much smaller than the other.
  3. When filling the grid, each cell depends only on adjacent cells.
  4. The cells don't have many possible values (usually only 2).

The third property is especially important, as it means that we can process the cells column-by-column (imagine a snake wrapping around the grid). We then only need to care about the rightmost processed cell in each row (hence the name "broken profile").

The fourth property suggests that we should use a bitmask to represent that broken profile.

Warning!

Note that the bitmask doesn't necessarily have to represent the state of the cells. In some problems (e.g. CEOI 2006 Connect), it can represent the state of the cell borders instead.

Focus Problem – try your best to solve this problem before continuing!

Tutorial

We'll process the grid cells column-by-column, row-by-row. Let ii and jj denote the row and column of the current cell we are considering, and dp[i][j][mask]\texttt{dp}[i][j][mask] be the number of ways to tile the grid so that:

  • All cells from cell (0,0)(0, 0) to cell (i,j1)(i, j - 1) are covered.
  • All cells from cell (i+1,j)(i + 1, j) to cell (N1,M1)(N - 1, M - 1) are empty.
  • maskmask represents whether each of the remaining NN cells are empty, with the kk-th bit corresponding to the cell in row kk.

For example, the following state would contribute toward dp[1][3][001012]\texttt{dp}[1][3][00101_2]: broken profile state example

The answer will be dp[N1][M1][0]\texttt{dp}[N - 1][M - 1][0].

We now have three cases when calculating dp[i][j][mask]\texttt{dp}[i][j][mask]:

  • The ii-th bit of the mask is 0, meaning that cell (i,j)(i, j) is covered.
    • Case 1: we used a horizontal tile to cover it.
      • Cell (i,j1)(i, j - 1) must have been empty, so there are dp[i1][j][mask2i]\texttt{dp}[i - 1][j][mask \oplus 2^i] ways to do this.
    • Case 2: we used a vertical tile to cover it.
      • This is only possible if i>0i > 0.
      • Cell (i,j1)(i,j-1) must have been covered and cell (i1,j)(i-1,j) must have been empty, so there are dp[i1][j][mask2i1]\texttt{dp}[i - 1][j][mask \oplus 2^{i - 1}] ways to do this.
      • This corresponds to if (i && !(mask & (1 << i)) && !(mask & (1 << i - 1))) in the code below.
  • The ii-th bit of the mask is 1, meaning that cell (i,j)(i, j) is empty.
    • Cell (i,j1)(i, j - 1) must have been covered, so there are dp[i1][j][mask2i]\texttt{dp}[i - 1][j][mask \oplus 2^i] ways to do this.
      • This is the same as case 1 of when the ii-th bit of the mask is 0, so we handle them simultaneously in the code below.

Note that the indices we need to use may become negative and will thus require wrapping. To simplify calculations and bypass this, simply drop the first two dimensions of the DP array, as dp[i][j]\texttt{dp}[i][j] depends only on dp[i1][j]\texttt{dp}[i - 1][j].

Code

Time Complexity: O(NM2N)\mathcal O(NM 2^N)

C++

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
int dp[1 << 10][2];
int main() {
int n, m;
cin >> n >> m;

Broken profile DP Problems

StatusSourceProblem NameDifficultyTags
CFNormal
Show TagsBroken Profile
COCINormal
Show TagsBroken Profile
CEOIHard
PlatinumVery Hard
Show TagsBroken Profile

Module Progress:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

PrevNext