Dynamic Programming – Ritambhara Technologies

Cutting the Rod Problem. Part_1: Recursion and Memoization

Given pieces of rod sizes. Find the max value we can get by cutting a rod of length n and selling the pieces.

Find minimum cost to travel to the destination railways station

There are N stations on a railway track. You are at the first station and you want to go to the final railway station. You […]

Number of ways to arrange tiles on a board

Given a board of size 2*n and tiles of dimension 1*2 each. In how many ways can we arrange the tiles so that entire board […]

Dynamic Programming concept

The basic idea of DP is applicable to problems that can be thought in terms of recursion. For example, consider problem of computing n’th fibonacci […]

How to prepare for Dynamic Programming Questions

The most difficult problems in Coding competitions and interviews of companies like Google, Microsoft etc. are from Dynamic Programming. DP as an approach to problem solving […]

Minimum edit distance of two strings

Given two strings of size m and n respectively, find the minimum number of operations required to transform one string into another. The following thee […]

Check if array can be divided in two parts with equal sum

Given an array of integers, write a function that returns true if it can be divided in two parts having equal sum. For example: If […]

Compute x^n (x to the power n)

Write a C function to compute xn which uses minimum number of multiplications. unsigned int power(double x, unsigned int n)

Kadane's Algorithm to find maximum subarray sum

Given an array of n integers (both +ve and -ve). Find the contiguous sub-array whose sum is maximum (More than 1 sub-array may have same […]