Dynamic Programming

• The computer science solution to such 1D tiling problems is a two pass algorithm called “Dynamic Programming”.

• For each prefix, the optimal length is the shortest sub-prefix before each valid suffix multigram.

To Encode the string “ABAA”

encode(“A”) = 1

encode(“AB”) = min(encode(“A”)+1,1) = 1

encode(“ABA”) = encode(“AB”)+1 = 2

encode(“ABAA”) = min(encode(“ABA”)+1,encode(“A”)+1) = 2

Previous slide

Next slide

Back to first slide

View graphic version