This is a very comprehensive 88-part course on competitive programming. It gets you from knowing basic programming to being a yellow-red rated coder on Codeforces / CodeChef / TopCoder / etc.

The primary objectives of this course are to learn about 30 different algorithms and data structures. The algorithm tutori...

In this tutorial we will be discussing dynamic programming on trees, a very popular algorithmic technique that solves many problems involving trees. We'll be learning this technique by example. We'll take a problem solving approach in this tutorial, not just describing what the final solution looks like, but walking through how one might go about solving such problems.

A first example

Task

Consider a tree in which every node has a positive value written on it. The task is to select several nodes from the tree (you may also select none), so that the sum of values of the nodes you select is maximized, and no two adjacent nodes are selected. The desired solution has complexity O(n).

General approach

Introduction

Computers can only do a limited number of operations in a given time, usually about a billion operations per second. Here, by an individual operation, we mean addition, multiplication, assigning a value to a variable, etc. Hence, if we want our algorithm to finish executing in a second or so, then we need to make sure that the total number of operations we are asking it to do is less than 1 billion.

Estimating the exact run-time of an algorithm without implementing and executing it is very tough since it depends on so many factors - including the programming language being used, the compiler, the hardware of the computer itself, and more. Instead, what we'd like to do most of the time, is to estimate the run-time approximately.

Rate of growth

In algorithms, we focus on estimating the execution ...

Since examples are the best way to go understand dynamic programming, here are three more classic dynamic programming problems. Make sure you either solve the each problem or try at least for a few hours before reading the solution.

Counting paths in a grid

You have a rectangular grid of points with n rows and n columns. You start at the bottom left corner. At each step, you can either go up to the next point in the same column or right to the next point in the same row. How many such paths are there from the bottom left corner to the top right corner?

What if some points are deleted (that is, no path ca...

Dynamic programming is a fancy name for storing intermediate results and re-using the stored result instead of re-computing them each time.

Let's see an example of a dynamic programming problem. Once we solve the problem using dynamic programming, the formal technical definitions will be easier to follow.

Tiling problem

Problem: You are given a grid of size n \times 2 and n tiles of size 2 \times 1. In how many different ways can you tile the grid such that the entire grid is covered and no tiles overlap. (The tiles look identical to each other. Two ways of tiling are different based on whether the tiles are placed horizontally or vertically).

Example: There are 3 possible ways of tiling a 3 \times 2 grid.

Tiling 1: 
Three vertical tiles
 __ __ __

Sieve of Eratosthenes is a way to compute prime factors of a number by pre-computing the smallest prime-factors of all numbers till a limit.

A great video tutorial by Khan Academy -

Also I recommend you to read this blog on CodeForces...