# Are there Dynamic programming speedups for $dp[i]=\min_{j<i}\{ f(a_j, a_i)\}$

I am wondering if there are dynamic programming speedups for the minimization problem $dp[i]=\min_{j<i}\{ f(a_j, a_i)\}$. Now I understand that its highly unlikely that such thing would exist for any arbitrary function $f$, but are there any speedups that can be applied if a certain condition is satisfied by $f$?

I am looking for any speedups that would make this DP a sub-$O(n^2)$ solution.

EDIT:

I have an array of $\{(a_1, b_1), ..., (a_n, b_n)\}$ tuples. I am trying to find a pair $i, j$ that minimizes $-\frac{|a_i-a_j|\times b_i \times b_j}{\max(|b_i|, |b_j|)}$ and hence my question.

• "dynamic programming speedups" -- that's not really a thing. Do you mean memoization? That always helps if function values are used multiple times. – Raphael Apr 10 '18 at 5:19
• FWIW, I don't see a recursion here. – Raphael Apr 10 '18 at 5:20
• A simple adversary argument shows that for a black box $f$ you need $\binom{n}{2}$ accesses to $f$. It's true that for some particular $f$ you can do better, for example for constant $f$. I suspect, however, that you do have a specific $f$ in mind. Perhaps you should tell us about it. – Yuval Filmus Apr 10 '18 at 6:48
• @YuvalFilmus Edited the question, I do indeed have an $f$ in mind but was seeing if I can generalize this. – AspiringMat Apr 10 '18 at 8:08
• Why write "minimise" and then an expression beginning with a negative sign, instead of just writing "maximise" and the expression? Anyway, since $|b_i|$ is in the formula, I presume the $b$-values can be negative. If so, a first step could be to see if any positive solution exists. The only way that all solutions can be negative is if $n=2$ and exactly one $b$-value is positive and the other is negative. Once you are certain a positive value exists, you can separately consider all pairs of negative $b$-values, and all pairs of positive $b$-values. – j_random_hacker Apr 10 '18 at 9:24