Given a dynamic programming formula like $f[i][j] = \min_{z<j}{f[i-1][z] + G[i][j-z]}$ where $G[i][j]$ is positive and increasing along $j$ for all $i$s. Is there any optimization to make it faster than $O(N^3)$?

  • $\begingroup$ I know that if $optz[i][j] ≤ optz[i][j + 1]$ (e.g., when G[i] is a convex and increasing function) then we can use convex hull technique to optimize this formula, but it seems that this doesn't apply to this case where $G[i]$ can be arbitrarily increasing sequence. $\endgroup$ – lz96 Feb 18 '19 at 8:31
  • $\begingroup$ Are you asking about this specific formula, or in general? Your use of "like" makes me unsure which you are asking about. $\endgroup$ – D.W. Feb 18 '19 at 20:34
  • $\begingroup$ @D.W. I'm referring to a set of DPs questions satisfying this formula. $\endgroup$ – lz96 Feb 18 '19 at 23:10
  • $\begingroup$ Sorry; I can't understand that answer. $\endgroup$ – D.W. Feb 19 '19 at 0:42

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.