Part of course:
Dynamic Programming (contd.)
- Counting paths in a grid
- Longest common substring
- Longest common subsequence
Since examples are the best way to go understand dynamic programming, here are three more classic dynamic programming problems. Make sure you either solve the each problem or try at least for a few hours before reading the solution.
You have a rectangular grid of points with n rows and n columns. You start at the bottom left corner. At each step, you can either go up to the next point in the same column or right to the next point in the same row. How many such paths are there from the bottom left corner to the top right corner?
What if some points are deleted (that is, no path can go through these points)?
The solution can be found at ICO Training Material.
Given two strings, S of length m and T of length n, find the longest strings which are substrings of both S and T. The algorithm should have complexity O(nm).
Given two strings, find the longest subsequence common both of them. This problem differs from problems of finding common substrings: unlike substrings, subsequences are not required to occupy consecutive positions within the original sequences.
Solutions to both the above problems can be found at ICO Training Material. Again, make sure you solve the problems or try for a few hours each before looking at the solutions.
If you get stuck, feel free to ask questions!