# Is there any optimization technique for DP with $f[i][j] = \min_{z<j}{f[i-1][z] + G[i][j-z]}$ where G[i] is increasing and positive?

Given a dynamic programming formula like $$f[i][j] = \min_{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)$$?

• 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. – lz96 Feb 18 '19 at 8:31