All About Programming: Dynamic Programming Optimizations

A[i][j] — the smallest k that gives optimal answer, for example in dp[i][j] = dp[i - 1][k] + C[k][j]
C[i][j] — some given cost function
We can generalize a bit in the following way: dp[i] = min_j < i{F[j] + b[j] * a[i]}, where F[j] is computed from dp[j] in constant time.
It looks like Convex Hull Optimization2 is a special case of Divide and Conquer Optimization.
It is claimed (in the references) that Knuth Optimization is applicable if C[i][j] satisfies the following 2 conditions:
quadrangle inequality: $\text{[math]}$
monotonicity: $\text{[math]}$
It is claimed (in the references) that the recurrence dp[j] = min_i < j{dp[i] + C[i][j]} can be solved in O(nlogn) (and even O(n)) if C[i][j] satisfies quadrangle inequality. WJMZBMR described how to solve some case of this problem.

Open questions:

Are there any other optimization techniques?
What is the sufficient condition of applying Divide and Conquer Optimization in terms of function C[i][j]? Answered

References:

"Efficient dynamic programming using quadrangle inequalities" by F. Frances Yao. find
"Speed-Up in Dynamic Programming" by F. Frances Yao. find
"The Least Weight Subsequence Problem" by D. S. Hirschberg, L. L. Larmore. find
"Dynamic programming with convexity, concavity and sparsity" by Zvi Galil, Kunsoo Park. find
"A Linear-Time Algorithm for Concave One-Dimensional Dynamic Programming" by Zvi Galil, Kunsoo Park. find

Labels