Dynamic Programming https://www.geeksforgeeks.org/knuths-optimization-in-dynamic-programming/

Knuth’s Optimization

Knuth’s optimization is a very powerful tool in dynamic programming, that can be used to reduce the time complexity of the solutions primarily from $O(N^3)$ to $O(N^2)$.

$dp[i][j]={\min }_{i\le k<j}(dp[i][k]+dp[k+1][j])+cost[i][j]$

The cost function must be a monotonic function?

The key is this following inequality: $opt[i][j-1]\le opt[i][j]\le opt[i+1][j]$