Dynamic Programming

This category contains all the posts which talks about dynamic programming. This is a child category to Algorithms

Solving 0/1 Knapsack problem using Dynamic Programming

Introduction A knapsack is a bag with straps, usually carried by soldiers to help them take their valuables or things which they might need during their journey. The 0/1 knapsack problem is a very famous interview problem. The problem statement is as follows: Given a set of items, each of which is associated with some weight and value. Find the subset of items which can be carried into the knapsack with weight limit W. It is required that the cumulative value of the items in the knapsack is maximum value possible. In simple words, it asks you to pick certain items from the set of items ...
Read More

Find Interleaving Strings using Dynamic Programming

Introduction This problem is already discussed in the post here. This post attempts to solve the same using the dynamic programming approach. Here is a brief description of the problem. Given three strings A, B and C such that A is "ab", B is "ade" and C is "adabe" find if C is an interleaving of A and B or not. Interleaving means constructing the third string C using the characters of A and B such that the characters in A and B preserve their relative ordering in C. In the above example C is an interleaving of A and B. Approach to Find Interleaving Strings using Dynamic Programming How ...
Read More

Dynamic Programming – CrazyNumbers

Problem Statement We are interested in finding the count of all N digit crazy numbers. Let us define a crazy number. A crazy number is a number where the magnitude of its consecutive digits differ by 1. For e.g.: Here is a list of all 2 digit crazy numbers: The total number of 2 digit crazy numbers is 17. You can notice that in all the numbers the digits differ only by 1. Similarly for three digit numbers the count reaches 32. For four digit numbers it becomes 61 and very soon it increases exponentially to 924903595810 for a 40 digit number. It might look like the a problem wh...
Read More

Dynamic Programming – Longest Palindromic Sequence

[nextpage title="Introduction"] Palindromes are fascinating character sequences in a string. A palindrome is a string which reads the same when read from either of the ends. This post in particular talks about palindromic sub sequences. To know more about a sub sequence, please check my post on Longest Common Sub sequence. A palindromic sequence means a sequence of characters which is a palindrome. Now, we must understand it clearly that we are talking about a sub sequence and not a substring. Understanding the Longest Palindromic Subsequence problem better It is really easy to say if...
Read More

Count Binary Search Trees created from N unique elements

[nextpage title="Introduction"] This is the third article for Binary Search Trees, to read more about the previous article, please check the topic Binary Search Tree Basics – a detailed discussion. To get updates on the coming articles in the series, please use the Subscribe feature on the right panel. Purpose of article This article explains few more aspects of binary search tree (BST). In the last article we learnt to construct a BST and then we revisited our technique to construct a better BST with the same. So this means that there can be more than one BST possible with a given set of e...
Read More

Dynamic Programming – Minimum Number of Coins

[nextpage title="Introduction"]This is the third post in Dynamic Programming - Online Classes. This is another article which demonstrates the usage of dynamic programming to solve a different problem in hand. To learn the basics of dynamic programming check my first article on dynamic programming. Purpose of the post The purpose of this article is to solve another problem using dynamic programming, this is a very famous interview question which is asked in multiple interviews. So without wasting any time, let us jump into the problem and ways to solve the same. Find minimum number of coi...
Read More

Dynamic Programming – Distinct Paths between two points

Introduction This is the second post in Dynamic Programming - Online Classes. This is another article which demonstrates the usage of dynamic programming to solve a different problem in hand. To learn the basics of dynamic programming check my first article on dynamic programming. Purpose of the article The purpose of this article is to solve another problem using dynamic programming, this is another very famous interview question which is asked in multiple interviews. So without wasting any time, let us jump into the problem and ways to solve the same. Count the number of distinct path...
Read More