Suppose I have a set of objects $X = \{ x_1, x_2, \cdots, x_n \} $ with some metric space defined $d: X \times X \to \mathbb{R}_+$. And i have is the gram matrix $G$ instead, $G \in \mathbb{R}^{n\times n}$, where $G_{ij} = d(x_i, x_j)$.
For any subset of $S \subseteq X$, I care about this quantity
$$ f(S) := \textbf{min} \sum_{i \in S} d(i, \alpha), \forall \alpha \in S $$
And my problem is how to select an optimal partition $(L, R) $ of $X$ from some set of partitions $P$ efficient, such that $f(L) + f(R)$ is minimized ?
$$ L^*, R^* = \textbf{argmin}_{(L, R) \in P} f(L) + f(R) $$
And $P$ has more than 1 element, so it's not a trivial problem.
A simple approach that would avoid some recomputation is to loop once through $P$, storing the values of $f(L)$ and $f(R)$, and updating the incumbent if $f(L)+f(R)$ is smaller. Each time you need to compute some $f(S)$, first check whether you already know its value from a previous step (memoization).