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.


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.

  • $\begingroup$ "dynamic programming speedups" -- that's not really a thing. Do you mean memoization? That always helps if function values are used multiple times. $\endgroup$ – Raphael Apr 10 '18 at 5:19
  • $\begingroup$ FWIW, I don't see a recursion here. $\endgroup$ – Raphael Apr 10 '18 at 5:20
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Apr 10 '18 at 6:48
  • $\begingroup$ @YuvalFilmus Edited the question, I do indeed have an $f$ in mind but was seeing if I can generalize this. $\endgroup$ – AspiringMat Apr 10 '18 at 8:08
  • $\begingroup$ 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. $\endgroup$ – j_random_hacker Apr 10 '18 at 9:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.