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…)

## Archive for the ‘dynamic_programming’ Category

### Count number of nodes in tree (DP)

August 7, 2018### SPOJ – ABA12C ( Buying Apples)

November 25, 2017User 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, 2017Given a list of coins and a target sum, find the number of ways to make that sum. (more…)

### Maximum SubArray – Leetcode

October 2, 2017Calculate the maximum sum between contiguous subarray. (more…)

### AIBOHP – SPOJ

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

### ACMAKER – SPOJ

September 28, 2017Given 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, 2017Given two string, find the longest subsequence matching substrings of at least k sizes. (more…)

### Mixtures – SPOJ

September 23, 2017Given 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, 2017Given 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, 2017Given 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…)