Introduction (Beginner) What is a dynamic programming, how can it be described? A DP is an algorithmic technique which is usually based on a recurrent formula and one (or some) starting states. A sub-solution of the problem is constructed from previously found ones. DP solutions have a polynomial complexity which assures a much faster running time than other techniques likebacktracking, brute-force etc. Now let's see the base of DP with the help of an example: Given a list of N coins, their values (V1, V2, ... , VN), and the total sum S. Find the minimum number of coins the sum of which is S (we can use asmany coins of one type as we want), or report that it's not possible to select coins in such a way that they sum up to S. Now let's start constructing a DP solution: First of all we need to find a state for which an optimal solution is found and with the help of which we can find the optimal solution for the nextstate. What does a "state" stand for? It's a way to describe a situation, a sub-solution for the problem. For example a state would be the solution for sum i, where i≤S. A smaller state than state i would be the solution for any sum j, where jS[i] ), we make S[i]=S[j]+1. This way we consecutively find the best solutions for each i, until last state N. Let's see what happens for a randomly generated sequence: 5, 3, 4, 8, 6, 7: I The length of the longest non-decreasing sequence of first i numbers The last sequence i from which we "arrived" to this one 1 1 1 (first number itself) 2 1 2 (second number itself) 3 2 2 4 3 3 5 3 3 6 4 5 Practice problem: Given an undirected graph G having N (10 ; S[i][j-1], if j>0) (where i represents the row and j the column of the table , its left-upper corner having coordinates {0,0} ; and A[i][j] being the number of apples situated in cell i,j). S[i][j] must be calculated by going first from left to right in each row and process the rows from top to bottom, or by going first from top to bottom in each column and process the columns from left to right. Pseudocode: For i = 0 to N - 1 For j = 0 to M - 1 S[i][j] = A[i][j] + max(S[i][j-1], if j>0 ; S[i-1][j], if i>0 ; 0) Output S[n-1][m-1]