Archive for the ‘dynamic_programming’ Category

Count number of nodes in tree (DP)

August 7, 2018

Number of nodes in a tree can be calculated from any node relating to its subtree. We can use dynamic programming to store count of subtree and add values to current node. (more…)


SPOJ – ABA12C ( Buying Apples)

November 25, 2017

User wants to buy K kilograms of apples for N friends, and each kilogram of apples has cost attached to it. If the cost is set as -1, then user cannot buy that. User can buy as many quantity of a particular kg of apple. Minimize the cost and see if all N friends can get apples with this selection, if not print -1. (more…)

Coin Change – HR

October 10, 2017

Given a list of coins and a target sum, find the number of ways to make that sum. (more…)

Maximum SubArray – Leetcode

October 2, 2017

Calculate the maximum sum between contiguous subarray. (more…)


September 28, 2017

Find the minimum number of characters that needs to be added to a string to make is palindrome. (more…)


September 28, 2017

Given a line that starts with acronym and has bunch of insignificant words. How many ways the acronym can be formed using significant (not insignificant) words so that each word has at least one char contributing to the acronym. (more…)

SAMER08D – DNA Sequences – SPOJ

September 26, 2017

Given two string, find the longest subsequence matching substrings of at least k sizes. (more…)

Mixtures – SPOJ

September 23, 2017

Given mixtures in a row. When they are mixed with each other, the result is modulus 100 of the sum. This replaces the mixing color. During mixing the process some smoke is generated (as by product), the quantity of which is the result of multiplication of two mixtures. Minimize the smoke generated when mixing two mixture. (more…)

Matrix Chain Multiplication (MCM)

September 23, 2017

Given the dimensions of matrices next to each other, find the best way to parenthesize (multiply the matrices) that minimized the number of multiplication. (more…)

Martian – SPOJ

September 19, 2017

Given a grid that contains two types of minerals B and Y. If the refinery to B are at top and Y are at left and the corresponding minerals gets collected if there is a straight path from that grid location all the way to the refinery. Maximize the total amount of mineral mined. (more…)