Dynamic programming making change algorithm Today we are going to discuss a new problem that can be solved using Dynamic Programming technique. We will talk about the well known problem of making change using a minimum number of coins. If you take the US currency as an example where we have the denominations (1C, 5C,
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 ..
Maximum Subsequence Sum Problem (MCSS) Before we get started let me remind you that this is a series of short articles on Dynamic Programming. You can refer to the first article (introduction) here. In this article we are going to discuss a new problem (MCSS) that can be solved efficiently using Dynamic Programming. The MCSS
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
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
Assembly Line Scheduling This is the second article on Dynamic Programming. You can refer to the first article (introduction) here. Let us get started by defining our problem. Problem definition The following bullet points define our problem: We have two (parallel) car assembly lines (1) and (2). Each assembly line has (n) stations. The time
Introduction This short article is mainly for students, software engineers and those who are struggling to get a grip on the subject. In other words I will not be focusing on the theoretical side of the topic. I will first explain what Dynamic Programming means then provide several examples to demonstrate this algorithmic technique. I
What is Recursion: Please Bear with me This is going to be a short and technical article so please bear with my bad English and writing style. Language is also a mean of communication and sometimes it fails to convey understanding so I will brain dump the concept in plain English to the best of
Introduction I am currently working at Yahoo one of the top Internet companies in the world. I also had the chance to work at PayPal the dominant company in online payments. When I lost my job in 2008 I had more than 30 phone interviews and several onsite interviews. Just to mention few names, I