DP_Optimizations.H File Reference

Classical DP optimization toolkit: D&C DP, Knuth, CHT, Li Chao, and monotone-queue transitions. More...

#include <algorithm>
#include <cstddef>
#include <limits>
#include <numeric>
#include <type_traits>
#include <utility>
#include <ah-errors.H>
#include <tpl_array.H>

Include dependency graph for DP_Optimizations.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	Aleph::Divide_Conquer_DP_Result< Cost >
	Result of divide-and-conquer partition DP optimization. More...
struct	Aleph::Knuth_Optimization_Result< Cost >
	Result of Knuth interval-DP optimization. More...
class	Aleph::Convex_Hull_Trick< T >
	Convex Hull Trick for minimum queries. More...
struct	Aleph::Convex_Hull_Trick< T >::Line
	Affine line y = m*x + b. More...
class	Aleph::Li_Chao_Tree< T >
	Li Chao tree for min line queries on an integral x-domain. More...
struct	Aleph::Li_Chao_Tree< T >::Line
	Affine line y = m*x + b. More...
struct	Aleph::Li_Chao_Tree< T >::Node
struct	Aleph::Monotone_Queue_DP_Result< Cost >
	Result of monotone-queue windowed DP transition. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.
namespace	Aleph::dp_optimization_detail

Typedefs
template<typename T >
using	Aleph::dp_optimization_detail::promoted_t = std::conditional_t< std::is_floating_point_v< T >, T, std::conditional_t<(sizeof(T)< 8), long long, __int128_t > >

Functions
template<typename T >
constexpr T	Aleph::dp_optimization_detail::default_inf () noexcept
template<typename Target , typename Source >
constexpr Target	Aleph::dp_optimization_detail::clamped_cast (Source val) noexcept
template<typename Cost , class Transition_Cost_Fn >
Divide_Conquer_DP_Result< Cost >	Aleph::divide_and_conquer_partition_dp (const size_t groups, const size_t n, Transition_Cost_Fn transition_cost, const Cost inf=dp_optimization_detail::default_inf< Cost >())
	Optimize partition DP using divide-and-conquer optimization.
template<typename Cost , class Interval_Cost_Fn >
Knuth_Optimization_Result< Cost >	Aleph::knuth_optimize_interval (const size_t n, Interval_Cost_Fn interval_cost, const Cost inf=dp_optimization_detail::default_inf< Cost >())
	Optimize interval DP with Knuth optimization.
Knuth_Optimization_Result< size_t >	Aleph::optimal_merge_knuth (const Array< size_t > &weights)
	Optimal adjacent merge cost via Knuth optimization.
template<typename Cost >
Monotone_Queue_DP_Result< Cost >	Aleph::monotone_queue_min_dp (const Array< Cost > &base_cost, const size_t window, const Cost inf=dp_optimization_detail::default_inf< Cost >())
	Optimize windowed min-transition DP with a monotone queue.
template<typename T >
Array< T >	Aleph::min_weighted_squared_distance_1d (const Array< T > &xs, const Array< T > &weights)
	Weighted squared-distance lower envelope on a line.

Detailed Description

Classical DP optimization toolkit: D&C DP, Knuth, CHT, Li Chao, and monotone-queue transitions.

This header collects optimization patterns that are frequently used to cut asymptotic complexity in dynamic programming recurrences:

• Divide & Conquer optimization for partition-like DP layers.
• Knuth optimization for interval DP under quadrangle-inequality assumptions.
• Convex Hull Trick (monotone slopes, min-query lower envelope).
• Li Chao Tree for arbitrary line insertion / min query on integral x-domain.
• Monotone-queue optimization for windowed transitions.

Additionally, it includes a geometric utility that applies Li Chao to the lower envelope of parabolas (weighted squared distances on a line).

Definition in file DP_Optimizations.H.