  Dynamic programming (DP) is one of the fundamental paradigms in algorithm
design. However, many DP algorithms have to fill in large DP tables,
represented by two-dimensional arrays, which causes at least quadratic running
times and space usages. This has led to the development of improved algorithms
for special cases when the DPs satisfy additional properties like, e.g., the
Monge property or total monotonicity.
  In this paper, we consider a new condition which assumes (among some other
technical assumptions) that the rows of the DP table are monotone. Under this
assumption, we introduce a novel data structure for computing
$(1+\varepsilon)$-approximate DP solutions in near-linear time and space in the
static setting, and with polylogarithmic update times when the DP entries
change dynamically. To the best of our knowledge, our new condition is
incomparable to previous conditions and is the first which allows to derive
dynamic algorithms based on existing DPs. Instead of using two-dimensional
arrays to store the DP tables, we store the rows of the DP tables using
monotone piecewise constant functions. This allows us to store length-$n$ DP
table rows with entries in $[0,W]$ using only polylog$(n,W)$ bits, and to
perform operations, such as $(\min,+)$-convolution or rounding, on these
functions in polylogarithmic time.
  We further present several applications of our data structure. For bicriteria
versions of $k$-balanced graph partitioning and simultaneous source location,
we obtain the first dynamic algorithms with subpolynomial update times, as well
as the first static algorithms using only near-linear time and space.
Additionally, we obtain the currently fastest algorithm for fully dynamic
knapsack.
