Part of list:

Dynamic Programming (contd.)

- Counting paths in a grid
- Longest common substring
- Longest common subsequence

Dynamic Programming (contd.)[ Edit ]

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,of lengthSandmof lengthT, find the longest strings which are substrings of bothnandS. The algorithm should have complexityT.O(nm)

Given two strings, find the longestcommon 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.subsequence

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!

Read more…(246 words)

Mark as completed

Part of lists:

Previous

[INOI1301] Calvins Game (INOI 2013: India)

Next

[AIBOHP] Aibohphobia

About the contributors:

Keshav DhandhaniaFormer TopCoder India rank #1, IOI medalist

99%

Kumar Harsh Sinha

1%

Loading…

Have a question? Ask here…

Post

Part of list:

Dynamic Programming (contd.)

- Counting paths in a grid
- Longest common substring
- Longest common subsequence

Contributors

Keshav DhandhaniaFormer TopCoder India rank #1, IOI medalist

99%

Kumar Harsh Sinha

1%

Ready to join our community?

Sign up below to automatically get notified of new lists, get **reminders** to finish ones you subscribe to, and **bookmark** articles to read later.

Continue with Facebook

— OR —

Your Full Name

Email address

I have an account. Log in instead

By signing up, you agree to our Terms and our Privacy Policy.