When [dynamic programming](Dynamic programming) is used to solve an optimization problem, often it is possible to speed up the algorithm by only looking at configurations that could possibly lead to an optimal solution, or in some way looking up the best configuration quickly.

## General techniques
Here we list some of the most general techniques.

### Convex hull trick
See [Convex hull trick]().

### Divide and conquer optimization
See [Divide and conquer optimization]().

### Knuth's optimization
See [Knuth's optimization](Knuth's optimization).

## Problems
- [Branch Assignment](https://open.kattis.com/problems/branch) [^1] [^2]

## See also
- [Dynamic programming]()

## External links
- [Dynamic Programming Optimizations](http://codeforces.com/blog/entry/8219)

[^1]: <https://www.youtube.com/watch?v=4xyhMgQnS88&list=PLm9puTBNlJjVbqpIkp048XbDNxK7-1Ucg&index=9>
[^2]: <http://www.csc.kth.se/~austrin/icpc/finals2016solutions.pdf>