Table of Contents:

Applications

Dynamic Programming (DP) …

Linux utility diff,

Fibonacci Numbers

Least Common Subsequence

Longest Increasing Subsequence

Longest Common Subsequence

Knapsack Problem

Break into house, and take items of most value

Solving Recurrences

Integral Images

SURF, Viola Jones rely upon fast computation of Integral Images for fast local feature detection and object detection. Dynamic Programming

Max-Pooling in ConvNets

[1]

Graphical Models

Koller and Friedman [2] use DP extensively. Variable Elimination (pp. 292-296, 337) for the summation of the joint distribution from the inside out, rather from the outside in, and cache the intermediate results to avoid repeated computation.

DP also arises in Belief Propagation (p. 356), Clique Tree Queries (p. 371), MAP and marginal MAP queries (p. 596).

References

[1]. Alessandro Giusti, Dan C. Cires¸an, Jonathan Masci, Luca M. Gambardella, Jurgen Schmidhuber. Fast Image Scanning with Deep Max-Pooling Convolutional Neural Networks. PDF.

[2]. Daphne Koller and Nir Friedman. Probabilistic Graphical Models: Principles and Techniques. 2009.