Tag: Dynamic Programming

Dynamic Programming Longest Increasing Sub Sequence

Longest Increasing Sub Sequence Welcome to the 6th part of our discussion on Dynamic Programming. You can refer to the first article (introduction) here. In this article we are going to discuss the "Longest Increasing Sub Sequence" problem which can be solved efficiently using Dynamic Programming. Problem Definition Given a sequence of numbers [A1 ..

Dynamic Programming Longest Common Subsequence

Longest Common Subsequence Welcome to the 4th article on Dynamic Programming. You can refer to the first article (introduction) here. I will be using the shortcut LCS to refer to longest common sub-sequence. Let us get started. Introduction One of the applications of "Longest Common Subsequence" problem is comparing DNA strings to see how similar

Dynamic Programming: Matrix Chain Multiplication

Matrix Chain Multiplication Welcome to the third article on Dynamic Programming. You can refer to the first article (introduction) here. Let us get started. Introduction Before we formally define our problem let us first refresh our memory about matrix multiplication. In order to multiply two matrices (A) and (B) the number of columns of matrix