Quadrangle-Inequality Optimization

Quadrangle-inequality optimization exploits decision monotonicity in a state transition and is also commonly called decision-monotonicity-optimized DP.

Basic knowledge

Consider the simplest case, in which we need to solve the following series of optimization problems:

Assume that the cost function $w(j,i)$ can be computed in $O(1)$ time.

In general, the total time complexity of these problems is $O(n^2)$, because for problem $i$ we must consider every possible decision $j$. When decision monotonicity holds, the decision space can be narrowed effectively, improving the total complexity.

• Decision monotonicity: for any $i_1 < i_2$, we have $\operatorname{opt}(i_1) \leq \operatorname{opt}(i_2)$.

The most common way to determine decision monotonicity is through the quadrangle inequality. In different contexts, this property is also called the Monge property (when describing a matrix $A_{j,i}$) or submodularity (when describing a function $f([j,i])$ whose variable is an interval).

• Quadrangle inequality: if, for every $a\leq b\leq c\leq d$,

  $$w(a,c)+w(b,d) \leq w(a,d)+w(b,c),$$

  then $w$ is said to satisfy the quadrangle inequality (abbreviated as “crossing no greater than containing”). If equality always holds, $w$ is said to satisfy the quadrangle identity.

Unless otherwise stated, we always assume $a\leq b\leq c\leq d$ below. The quadrangle inequality is a sufficient but not necessary condition for decision monotonicity.

The quadrangle inequality can be understood as saying that, on a suitable domain, the cost function $w$ has a nonpositive second mixed difference $\Delta_i\Delta_jw(j,i)$.

Using decision monotonicity, many common algorithms can optimize their time complexity to $O(n\log n)$. These algorithms differ in their applicable ranges, implementation difficulty, and running efficiency, so the appropriate algorithm must be chosen for the actual setting. This mainly depends on the properties of $w(j,i)$. Unless otherwise stated, this article assumes that $w(i,j)$ supports random access, meaning that $w(j,i)$ can be queried or computed in $O(1)$ time. However, $w(j,i)$ is not always so easy to compute. Therefore, in addition to the basic case, we discuss methods for optimizing DP with decision monotonicity when $w(j,i)$ has only the following properties:

• Moving access: $w(j,i)$ can be obtained from $w(j\pm 1,i)$ or $w(j,i\pm 1)$ by an $O(1)$-time transition. (This is similar to the situation in Mo's algorithm.)
• Dynamic computation: computing $w(j,i)$ depends on $\{f(j'):j' < j\}$. This means that $f$ and $w$ can only be computed in order. The interval-partition problem without a limit on the number of intervals introduced below belongs to this case.

These two properties are not mutually exclusive: $w(j,i)$ may require dynamic computation while supporting only moving access.

Divide and conquer

To solve all states, it is enough to solve all optimal decision points. For every $1 \leq i \leq n$, solve $\operatorname{opt}(i)$ by first computing $\operatorname{opt}(n/2)$, then separately computing, for $1 \leq i < n/2$ and for $n/2 < i \leq n$, $\operatorname{opt}(i)$. At this point, $\operatorname{opt}(i)$ for the first half is known to lie between $1$ and $\operatorname{opt}(n/2)$, inclusive, while $\operatorname{opt}(i)$ for the second half is known to lie between $\operatorname{opt}(n/2)$ and $n$, inclusive. Process the two subintervals in the same way until the optimal decision for every problem has been computed. Recording the upper and lower search bounds during the divide-and-conquer process keeps the complexity at $O(n\log n)$. The recursion tree has $O(\log n)$ levels, and each decision point is computed at most twice at each level, so the total number of computations is $O(n\log n)$.

val_t w(int j, int i);  // Cost function
val_t f[N];             // Optimal value
int opt[N];             // Smallest optimal decision

// Recursively solve the problems in [l,r]
// Their smallest optimal decision points are known to lie in [opt_l, opt_r]
void calc(int l, int r, int opt_l, int opt_r) {
  int mid = (l + r) / 2;
  // Find the optimal decision point for problem mid
  for (int j = opt_l; j <= std::min(opt_r, mid); ++j) {
    if (w(j, mid) < f[mid]) {
      f[mid] = w(j, mid);
      opt[mid] = j;
    }
  }
  // Derive the decision intervals of the two parts from decision monotonicity, then recurse
  if (l < mid) calc(l, mid - 1, opt_l, opt[mid]);
  if (r > mid) calc(mid + 1, r, opt[mid], opt_r);
}

// Solve the problems on the whole interval [1,n]
void solve(int n) {
  // The array f must be cleared before every call to the recursive function
  std::fill(f + 1, f + n + 1, inf);
  // Initially, we only know that every decision for the problems in [1,n] lies in [1,n]
  calc(1, n, 1, n);
}

Besides the basic random-access case, the divide-and-conquer algorithm can also handle the case where $w(j,i)$ supports only moving access. During the computation, maintain a cursor $(j,i)$ and the corresponding value $w(j,i)$; whenever a new value is needed, move the cursor directly to the new position and update the function value. The time complexity remains $O(n\log n)$. For a more detailed discussion, see the section Simplified LARSCH algorithm below. However, divide and conquer cannot handle the case where $w(j,i)$ must be computed dynamically, because it cannot compute the smallest optimal decision $\operatorname{opt}(n/2)$ at the midpoint before the problems in the left half have been solved.

Binary-decision queue

Notice that, for each decision point $j$, the problems $i$ for which it can be the smallest optimal decision necessarily form an interval. A monotone queue can record the problem interval that each decision point can solve so far; the optimal solution for a problem can then be obtained naturally from the decision points stored in the queue.

More specifically, the algorithm scans decision points in order. When it reaches decision point $k$, the queue stores a triple consisting of each feasible decision point $j$ considered so far and the left and right endpoints $l_j$ and $r_j$ of the interval of problems it can solve. For a problem in the interval $[l_j,r_j]$, $j$ is the smallest optimal decision among all decision points considered so far (that is, the decision points in $[1,k]$). At any moment, the decision points stored in the queue need not be consecutive, but the unresolved problems $[j,n]$ should be the disjoint union of the problem intervals stored in the queue.

To show that, during queue updates, decision point $j$ is the smallest optimal decision for a contiguous interval of problems $i$, we need to strengthen the preceding conclusion slightly:

The algorithm proceeds as follows:¹

• Initially, the queue is empty. As in a monotone queue, when considering each next decision $j$, perform both a dequeue and an enqueue operation.
• Dequeue: first remove the previous problem $j-1$ from the queue. If the right endpoint of the problem interval solvable by the decision at the front of the queue is exactly $j-1$, pop the front directly; otherwise, update the left endpoint of the interval solvable by the front decision to $j$.
• Enqueue: to enqueue decision $j$, first compare it with the decision $j'$ at the back of the queue.
  • If, for problem $l_{j'}$, the decision $j$ being enqueued is strictly better than the existing decision $j'$, namely $w(j,l_{j'}) < w(j',l_{j'})$, pop the decision $j'$ from the back. Continue until the queue is empty or the decision $j'$ at the back is better than $j$ for problem $l_{j'}$.
  • If the queue is empty, enqueue $(j,j,n)$, meaning that decision $j$ is the optimal solution for all unresolved problems.
  • If the decision $j'$ at the back of the queue is no worse, for problem $r_{j'}$, than the decision $j$ being enqueued, then, when $r_{j'} < n$, enqueue $(j,r_{j'}+1,n)$, meaning that $j$ is the smallest optimal decision for the problems $[r_{j'}+1,n]$. Otherwise, do not enqueue $j$, because it is not better than the existing decision.
  • The final case is that the decision $j'$ at the back is strictly better than the decision $j$ being enqueued for problem $l_{j'}$, but strictly worse for problem $r_{j'}$. This means that there is a problem $i\in(l_{j'},r_{j'}]$ such that the smallest optimal decision for the problems $[l_{j'},i-1]$ is $j'$ and the smallest optimal decision for the problems $[i,r_{j'}]$ is $j$. Therefore, use binary search to find the smallest $i\in[l_{j'},r_{j'}]$ satisfying $w(j,i) < w(j',i)$, change the right endpoint $r_{j'}$ of the interval at the back of the queue to $i-1$, and enqueue $(j,i,n)$.
• Once decision $j$ has been processed, all decisions up to $j$ have been processed. The decision at the front of the queue is then the smallest optimal decision for problem $j$, so record the corresponding optimal solution.

val_t w(int j, int i);  // Cost function
val_t f[N];             // Optimal value
int opt[N];             // Smallest optimal decision
int lt[N], rt[N];       // Problem interval [l_j,r_j] solvable by decision j

// Solve the problems on the whole interval [1,n]
void solve(int n) {
  std::deque<int> dq;  // Monotone queue storing all feasible decisions

  // Consider all problems and decisions in order; indices start at 1
  for (int j = 1; j <= n; ++j) {
    // Dequeue
    if (!dq.empty() && rt[dq.front()] < j) dq.pop_front();
    if (!dq.empty()) lt[dq.front()] = j;
    // Enqueue
    while (!dq.empty() && w(j, lt[dq.back()]) < w(dq.back(), lt[dq.back()])) {
      dq.pop_back();
    }
    if (dq.empty()) {
      lt[j] = j;
      rt[j] = n;
      dq.emplace_back(j);
    } else if (w(j, rt[dq.back()]) >= w(dq.back(), rt[dq.back()])) {
      if (rt[dq.back()] < n) {
        lt[j] = rt[dq.back()] + 1;
        rt[j] = n;
        dq.emplace_back(j);
      }
    } else {
      int ll = lt[dq.back()], rr = rt[dq.back()], i = rr;
      // Binary search
      while (ll <= rr) {
        int mm = (ll + rr) / 2;
        if (w(j, mm) < w(dq.back(), mm)) {
          i = mm;
          rr = mm - 1;
        } else {
          ll = mm + 1;
        }
      }
      rt[dq.back()] = i - 1;
      lt[j] = i;
      rt[j] = n;
      dq.emplace_back(j);
    }
    // Compute
    f[j] = w(dq.front(), j);
    opt[j] = dq.front();
  }
}

As in a monotone queue, each decision point is enqueued at most once and dequeued at most once. Dequeue is $O(1)$, while enqueue is $O(\log n)$ because it may require binary search, so the total time complexity is $O(n\log n)$.

Because the binary-decision queue algorithm considers all problems and decision points in order, it can handle cases where $w(j,i)$ requires dynamic computation. This is its advantage over divide and conquer. However, because the binary-search step in the algorithm relies on random access to $w(j,i)$, it cannot handle the case where $w(j,i)$ supports only moving access.

#include <algorithm>
#include <cmath>
#include <deque>
#include <iostream>
#define all \
  for (auto i : {&q, &l, &r}) (*i)
using namespace std;
int n, a[500009], ans[500009];
deque<int> q, l, r;

double f(int i, int j) { return a[i] + sqrtl(j - i); }

void work() {
  all.clear();
  for (int i = 0; i < n; ++i) {
    if (q.size() && r.front() < i) all.pop_front();  // Dequeue from the front
    if (q.size()) l.front() = i;
    for (; q.size() && f(q.back(), l.back()) <= f(i, l.back());)  // Dequeue from the back
      all.pop_back();
    if (q.empty())  // Enqueue
      q.emplace_back(i), l.emplace_back(i), r.emplace_back(n);
    else if (f(q.back(), n) < f(i, n)) {
      int ll = l.back(), rr = n, mid;
      for (; ll <= rr;) {
        mid = (ll + rr) >> 1;
        if (f(q.back(), mid) < f(i, mid))
          rr = mid - 1;
        else
          ll = mid + 1;
      }
      r.back() = rr;
      q.emplace_back(i), l.emplace_back(ll), r.emplace_back(n);
    }
    ans[i] = max(ans[i], (int)(ceil(f(q.front(), i))) - a[i]);
  }
}

int main() {
  cin >> n;
  for (int i = 0; i < n; cin >> a[i++]);
  work();
  reverse(a, a + n);
  reverse(ans, ans + n);
  work();
  reverse(ans, ans + n);
  for (int i = 0; i < n; cout << ans[i++] << '\n');
}

Simplified LARSCH algorithm

The preceding two algorithms cannot handle the case where $w(j,i)$ requires both dynamic computation and moving access. This section introduces an algorithm that overcomes both difficulties at once. It is a simplified version of the LARSCH algorithm² proposed by Larmore and Schieber in 1991, hence the name simplified LARSCH algorithm. The original algorithm can solve decision-monotone DP problems in $O(n)$ time, but its implementation is more complicated and is not covered here.

We still use divide and conquer. When solving the problems in the interval $(l,r]$, assume that we know:

• for problems in $[1,l]$, the smallest optimal decision for problem $i$ is $\operatorname{opt}(i)$, together with its optimal value, and
• when only decisions in $[1,l]$ are considered, the smallest optimal decision for problem $r$ is $\operatorname{opt}_l(r)$, together with its optimal value.

When solving the problems in $(l,r]$ is complete, we need the smallest optimal decision and optimal value for every problem in $(l,r]$.

Let $\textit{mid}$ be the midpoint of $(l,r]$. The process is:

1. Iterate over decisions $i\in[\operatorname{opt}(l),\operatorname{opt}_l(r)]$, updating the smallest optimal decision and optimal value for problem $\textit{mid}$.
2. Recursively solve the problems in $(l,\textit{mid}]$.
3. Iterate over decisions $i\in(l,\textit{mid}]$, updating the optimal value for problem $r$.
4. Recursively solve the problems in $(\textit{mid},r]$.

Before recursing on the whole interval $[1,n]$, first use decision $j=1$ to update problems $i\in\{1,n\}$. The algorithm terminates when the recursion reaches $l=r$.

val_t w(int j, int i);  // Cost function
val_t f[N];             // Optimal value
int opt[N];             // Smallest optimal decision

// Update problem i with decision j
void check(int j, int i) {
  if (w(j, i) < f[i]) {
    f[i] = w(j, i);
    opt[i] = j;
  }
}

// Recursively solve the problems in (l, r]
void calc(int l, int r) {
  int mid = (l + r + 1) / 2;
  for (int j = opt[l]; j <= opt[r]; ++j) check(j, mid);
  if (mid < r) calc(l, mid);
  for (int j = l + 1; j <= mid; ++j) check(j, r);
  if (mid > l) calc(mid, r);
}

// Solve the problems on the whole interval [1, n]
void solve(int n) {
  // Clear the array f
  std::fill(f + 1, f + n + 1, inf);
  // Initialization
  check(1, 1);
  check(1, n);
  // Recursively solve the problems in (1, n]
  calc(1, n);
}

First, we can establish the correctness of this algorithm. It is enough to check that the prerequisites stated above hold before every recursive step (steps 2 and 4). By Corollary 1 from the preceding section, $\operatorname{opt}(l)=\operatorname{opt}_l(l)\le\operatorname{opt}_l(\textit{mid})\le\operatorname{opt}_l(r)$. Thus, after step 1, $\operatorname{opt}_l(\textit{mid})$ is known, so the prerequisites for recursively solving the problems in $(l,\textit{mid}]$ hold before step 2. Since $\{\operatorname{opt}(i):i\in[1,l]\}$ was already known, step 2 additionally obtains the values of $\{\operatorname{opt}(i):i\in(l,\textit{mid}]\}$, so after it $\{\operatorname{opt}(i):i\in[1,\textit{mid}]\}$ is known. At the same time, since $\operatorname{opt}_l(r)$ was already known, after step 3, $\operatorname{opt}_\textit{mid}(r)$ is known as well. Therefore, the prerequisites for recursively solving the problems in $(\textit{mid},r]$ also hold before step 4.

Next, we show that the complexity remains $O(n\log n)$. The recursion tree has $O(\log n)$ levels. For each node at the same level of the recursion tree, the algorithm iterates over the decisions in $[\operatorname{opt}(l),\operatorname{opt}_l(r)]$ and $(l,\textit{mid}]$, respectively. Since $\operatorname{opt}(l)\le\operatorname{opt}_l(r)\le\operatorname{opt}(r)$, each decision point is traversed $O(1)$ times at any one level. Therefore, the total number of traversals at each level is $O(n)$. If one access or computation of $w(j,i)$ takes $O(1)$ time, the algorithm has time complexity $O(n\log n)$.

For cases where $w(j,i)$ supports only moving access, the complexity of this algorithm is still $O(n\log n)$. In this case, maintain separately for steps 1 and 3 a cursor $(j,i)$ and the current value of $w(j,i)$. Whenever a new value is needed, move the cursor $(j,i)$ directly from its previous position to the new position and transition the value of $w(j,i)$. It is easy to verify that the total number of such direct updates while traversing the recursion tree is $O(n\log n)$. Therefore, the time complexity remains $O(n\log n)$.

Because this algorithm computes the problems in $(l,r]$ only after computing the optimal values in $[1,l]$, including $f(i)$, it can also handle cases where $w(j,i)$ requires dynamic computation.

Interval-partition problem

Consider partitioning an interval into several subintervals. Formally, partition the given interval $[1,n]$ into $[a_1,b_1],\cdots,[a_k,b_k]$, where $a_1=1$, $b_k=n$, and $b_{i}+1=a_{i+1}$ for every $i < k$. The cost of a partition is $\sum_{i=1}^kw(a_i,b_i)$. The goal is to minimize this cost. The following 1D1D state transition can be written:

Here, $f(0)=0$. If $w(j,i)$ satisfies the quadrangle inequality, then $f(j-1)+w(j,i)$ necessarily satisfies it as well, because the first term contains no crossing term involving $j$ and $i$ and therefore cancels in the mixed difference. However, because the cost function depends on preceding subproblems, this transition can only be computed in order. Therefore, it cannot use the first divide-and-conquer algorithm described above and is generally suitable only for the binary-decision queue or simplified LARSCH algorithm. The time complexity is $O(n\log n)$.

Fixed number of intervals

The problem above can be strengthened by fixing the number of intervals: partition the interval into exactly $m$ subintervals. The number of intervals after partitioning becomes one dimension of the state. The corresponding 2D1D transition is:

Here, $f(0,0)=0$, while $f(0,i)=f(k,0)=\infty$ for every $1\leq k\leq m$ and $1\leq i\leq n$. By the same reasoning as above, $f(k-1,j-1)+w(j,i)$ necessarily satisfies the quadrangle inequality. The computation of layer $i$ no longer depends on results from that same layer, so every layer can be computed using any algorithm described in the preceding section. The time complexity is $O(mn\log n)$.

For this problem, decision monotonicity also permits other optimization algorithms. The second approach relies on the following result and is very similar to the Knuth optimization algorithm described in detail below.

Using this result, we can restrict the search range of decision $j$. In the implementation, traverse $k$ forward and $i$ backward; brute-force search over $j$ within the previously established bounds guarantees $O(n(n+m))$ time.

The final optimization method starts from the following observation.

This result guarantees that the problem can be solved by WQS binary search (called the Aliens trick abroad). Specifically, consider the parameterized cost function $w_c(j,i):=w(j,i)+c$ and solve the problem without a limit on the number of intervals, obtaining the optimal value $f_c(n)$. As the real parameter $c$ increases, the number of intervals in the corresponding optimum decreases monotonically. Therefore, binary search can find the parameter for which the optimal number of intervals is exactly $m$; denote this parameter by $c$. The optimum of the original problem is $f(n,m) = f_c(n)-cm$. Here, the real number $c$ can be viewed as the Lagrange multiplier for the interval-count constraint. The implementation has many details; see the WQS binary search page. Its time complexity is $O(n\log n\log C)$, where $C$ is a constant.

The three algorithms for interval partitioning with a fixed number of intervals have different advantages at different data scales; choose one according to the specific problem.

#include <iostream>
constexpr int N = 3009;
constexpr int M = 309;
using namespace std;
int n, m, a[N], s[N], g[M][N], p[M][N];

int f(int i, int j) {
  int k = (i + j) >> 1;
  return a[k] * (k - i + 1) - (s[k] - s[i - 1]) + (s[j] - s[k]) -
         a[k] * (j - k);
}

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; cin >> a[i], s[i] = s[i - 1] + a[i], ++i);
  for (int i = 1; i <= n; ++i) g[0][i] = 1 << 30, p[m + 1][i] = i;
  for (int i = 1; i <= m; ++i) p[i][0] = 1;
  for (int i = 1; i <= n; ++i)
    for (int j = m; j; --j) {
      g[j][i] = 1 << 30;
      for (int k = p[j][i - 1]; k <= p[j + 1][i]; ++k) {
        int tmp = g[j - 1][k - 1] + f(k, i);
        if (tmp < g[j][i]) g[j][i] = tmp, p[j][i] = k;
      }
    }
  cout << g[m][n];
}

#include <deque>
#include <iostream>
#define all \
  for (auto i : {&q, &l, &r}) (*i)
using namespace std;
long long n, m, a[500009], s[500009], u, v, w, sum[500009], cnt[500009];
deque<int> q, l, r;

long long f(int i, int j) {
  int k = (i + j) >> 1;
  return sum[i - 1] + v + a[k] * (k - i + 1) - (s[k] - s[i - 1]) +
         (s[j] - s[k]) - a[k] * (j - k);
}

void work() {
  all.clear();
  for (int i = 1; i <= n; ++i) {
    if (q.size() && r.front() < i) all.pop_front();  // Dequeue from the front
    if (q.size()) l.front() = i;
    for (; q.size() && f(q.back(), l.back()) >= f(i, l.back());)  // Dequeue from the back
      all.pop_back();
    if (q.empty())  // Enqueue
      q.emplace_back(i), l.emplace_back(i), r.emplace_back((int)n);
    else if (f(q.back(), n) >= f(i, n)) {
      int ll = l.back(), rr = n, mid;
      for (; ll <= rr;) {
        mid = (ll + rr) >> 1;
        if (f(q.back(), mid) >= f(i, mid))
          rr = mid - 1;
        else
          ll = mid + 1;
      }
      r.back() = rr;
      q.emplace_back(i), l.emplace_back(ll), r.emplace_back((int)n);
    }
    sum[i] = f(q.front(), i);
    cnt[i] = cnt[q.front() - 1] + 1;
  }
}

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; cin >> a[i], s[i] = s[i - 1] + a[i], ++i);
  for (w = 2e12; u <= w;) {  // WQS binary search
    v = (u + w) >> 1;
    work();
    if (cnt[n] < m)
      w = v - 1;
    else
      u = v + 1;
  }
  v = w;
  work();
  cout << sum[n] - m * v;
}

Interval-merging problem

Another class of dynamic programs that can be optimized by the quadrangle inequality is the interval-merging problem: repeatedly merge the $n$ unit intervals $[i,i]$ until obtaining $[1,n]$. Each time $[j,k]$ and $[k+1,i]$ are merged, pay cost $w(j,i)$. The goal is to find a merging order with minimum total cost. The corresponding 2D1D transition is:

The initial cost is $f(i,i)=0$. The brute-force algorithm has total complexity $O(n^3)$, while decision monotonicity reduces it to $O(n^2)$. This algorithm was first proposed by Knuth for the optimal binary search tree problem and was further studied and summarized by Yao Chufeng; internationally it is called Knuth's optimization or the Knuth–Yao speedup.

In addition to the quadrangle inequality, decision monotonicity for interval merging requires the cost function to satisfy interval-containment monotonicity.

• Interval-containment monotonicity: if, for all $a \leq b \leq c \leq d$,

  $$w(b,c) \leq w(a,d),$$

  then $w$ is said to be monotone under interval containment.

This is essentially a first-order condition on the cost function: $w(j,i)$ decreases with $j$ and increases with $i$.

Using this result, we can likewise restrict the search range of decision point $k$. Traverse interval lengths $i-j+1$ in increasing order, then traverse all intervals $[j,i]$ of that length. Brute-force all $k$ between $\operatorname{opt}(j,i-1)$ and $\operatorname{opt}(j+1,i)$ to obtain $f(j,i)$ and record $\operatorname{opt}(j,i)$. For each fixed length, the total decision-space size is $O(n)$, and there are $O(n)$ possible lengths, so the total complexity is $O(n^2)$.

val_t w(int j, int i);  // Cost function
val_t f[N][N];          // Optimal values
int opt[N][N];          // Smallest optimal decisions

// Solve the problem for the whole interval [1,n]
void solve(int n) {
  // Initialize
  for (int i = 1; i <= n; ++i) {
    f[i][i] = 0;
    opt[i][i] = i;
  }
  // Enumerate interval lengths
  for (int len = 2; len <= n; ++len) {
    // Enumerate all intervals of length len
    for (int j = 1, i = len; i <= n; ++j, ++i) {
      f[j][i] = inf;
      for (int k = opt[j][i - 1]; k <= opt[j + 1][i]; ++k)
        if (f[j][i] > f[j][k] + f[k + 1][i] + w(j, i)) {
          f[j][i] = f[j][k] + f[k + 1][i] + w(j, i);  // Update the state value
          opt[j][i] = k;  // Update the (smallest) optimal decision
        }
    }
  }
}

Classes of functions satisfying the quadrangle inequality

The following properties make it easier to prove that a function satisfies the quadrangle inequality.

Property 1: If $w_1(j,i)$ and $w_2(j,i)$ both satisfy the quadrangle inequality (or interval-containment monotonicity), then for any $c_1,c_2\geq 0$, $c_1w_1+c_2w_2$ also satisfies the same property.