Consecutive-block Bellman recurrence and oracle cost schedule
DefinitionFBMSP_DynamicProgramThis bundle defines a finite maximum, the consecutive-block Bellman recurrence, and an inductive relation witnessing a partition and its score. Its first parameter counts additional slots beyond an initial block; a -price problem uses . Empty blocks are permitted and should have zero score in the pricing application.
The cost layer counts nonempty block-oracle queries, Bellman candidate evaluations in a bottom-up table, arbitrary declared oracle charges, and reconstruction steps. These counts describe a specified memoized evaluation schedule. They do not claim that naive recursive evaluation has quadratic cost or that arbitrary real-valued oracle operations have unit bit complexity.
import Mathlib
noncomputable section
open scoped BigOperators
namespace FBMSP
/-- A maximum over the integers 0,...,n. -/
def prefixMax (f : ℕ → ℝ) : ℕ → ℝ
| 0 => f 0
| n + 1 => max (prefixMax f n) (f (n + 1))
/-- k additional block slots, hence k+1 slots in total, on [a,a+n). -/
def intervalDP (W : ℕ → ℕ → ℝ) : ℕ → ℕ → ℕ → ℝ
| 0, a, n => W a (a + n)
| k + 1, a, n =>
prefixMax (fun i => intervalDP W k a i + W (a + i) (a + n)) n
inductive IntervalValue (W : ℕ → ℕ → ℝ) : ℕ → ℕ → ℕ → ℝ → Prop
| one (a n : ℕ) : IntervalValue W 0 a n (W a (a + n))
| append {k a n i : ℕ} {v : ℝ} (hi : i ≤ n)
(hv : IntervalValue W k a i v) :
IntervalValue W (k + 1) a n (v + W (a + i) (a + n))
/-- Nonempty interval queries, counted by right endpoint. -/
def blockOracleCalls : ℕ → ℕ
| 0 => 0
| n + 1 => blockOracleCalls n + (n + 1)
/-- Bottom-up table schedule: k extra layers, columns 0,...,n, i+1 cuts
at column i. This is not the cost of naive recursive evaluation. -/
def tableCandidateEvaluations (k n : ℕ) : ℕ := k * blockOracleCalls (n + 1)
/-- One query costs m including the price and attained value; a Bellman
candidate is one arithmetic/comparison unit. Empty intervals cost zero. -/
def tableWork (k n m : ℕ) : ℕ :=
m * blockOracleCalls n + tableCandidateEvaluations k n
/-- Actual declared charges of the primitive price-and-value oracle,
enumerating each nonempty interval exactly once by its right endpoint. -/
def oracleCharges (charge : ℕ → ℕ → ℕ) : ℕ → ℕ
| 0 => 0
| n + 1 => oracleCharges charge n + ∑ a ∈ Finset.range (n + 1), charge a (n + 1)
/-- Cost of the memoized schedule with K slots: oracle precomputation,
Bellman candidates for K-1 extra layers, and K backtracking steps. -/
def segmentationWork (charge : ℕ → ℕ → ℕ) (K n : ℕ) : ℕ :=
oracleCharges charge n + tableCandidateEvaluations (K - 1) n + K
end FBMSP
Read-back
What the Lean code literally says, in plain math · gpt-6-astra
For any function , its prefix maximum at is , recursively initialized by and extended by taking the maximum with ; in particular a prefix of length parameter contains the value at . For any function , define and, for natural , . The relation saying that is an interval value at is the relation generated by the following two rules: is a value at ; and if and is a value at , then is a value at . Equivalently, its values are exactly over natural nondecreasing cuts and . Thus counts additional slots beyond the first, for blocks in total; zero-length blocks are included. There is no assumption on , including no assumption that , so at the sole value and the recurrence both equal . Define and , equivalently . The table candidate evaluation count at natural parameters is . The table work at natural parameters is ; this is an explicitly defined natural number and contains no machine, implementation, or measured-runtime relation. All these definitions allow zero parameters: , the candidate count is at , and . For any charge function , define the total charge and , equivalently . Only nonempty intervals with endpoints between and occur in this sum; diagonal and out-of-range charges do not occur. For a natural number of slots , the segmentation work is the defined number , with natural subtraction . Thus this expression adds the supplied interval charges, the candidate count for additional layers, and ; it imposes no connection between and a computational implementation. At it equals , and at it equals .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.