For definition and explanation please refer to the following post. This post is only implementation in Python. Python code # Function recieves the input array A def MCSS (A): # Auxiliary array B = # MCSS ending at position 0 is just the first element B.append(A[0]) # Populate B for i in range (1,

Integer Knapsack Problem Welcome! This is part 10 in a series of articles on Dynamic Programming. You can refer to the first part (introduction) by clicking here. Today we are going to discuss the “Integer Knapsack Problem”. Please recall that our problem today is a little bit different from the "01 Knapsack Problem" in which

Moving on a Checkerboard Welcome to a new article on Dynamic Programming. Today we will discuss "Moving on a Checkerboard" problem. This is part 9 of a series of articles on the topic. You can refer to the first article here. Let us get started. Problem Definition We are given a grid of squares or

Edit Distance or Levenshtein Distance Welcome! This is part eight in a series of articles on Dynamic Programming. You can start at the beginning of this series if you wish by clicking here. Today we are going to talk about “Edit Distance” or “Levenshtein distance” problem which has many applications such as spell checking. Let

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