

Revision History 

Subsets of a given set
The problems of this type has some set X. The number of elements in this set is small: less than 20. The idea of DP solution is to consider all subsets of X as state domain. Often there are additional parameters. So generally we have state domain in form (s,a) where s is a subset of X and "a" represents additional parameters.
Consider TSP problem as an example. The set of cities X={0, 1, 2, ..., N1} is used here. State domain will have two parameters: s and a. The state (s,a)>R means that R is the shortest path from city 0 to city "a" which goes through all the vertices from subset s exactly once. The transition is simply adding one city v to the end of path: (s,a)>R turns into (s+{v},v)>R + M[a,v]. Here M[i,j] is distance between ith and jth city. Any hamiltonian cycle is a path which goes through each vertex exactly once plus the edge which closes the cycle, so the answer for TSP problem can be computed as min(R[X,a]+M[a,0]) among all vertices "a".
It is very convenient to encode subsets with binary numbers. Look recipe "Representing sets with bitfields" for detailed explanation.
The state domain of DP over subsets is usually ordered by set inclusion. Each forward transition adds some elements to the current subset, but does not subtract any. So result for each state (s,a) depends only on the results of states (t,b) where t is subset of s. If state domain is ordered like this, then we can iterate through subsets in lexicographical order of binary masks. Since subsets are usually represented with binary integers, we can iterate through all subsets by iterating through all integers from 0 to 2^N  1. For example in TSP problem solution looks like:
int res[1<<N][N];
memset(res, 63, sizeof(res)); //filling results with positive infinity
res[1<<0][0] = 0; //DP base
for (int s = 0; s < (1<<N); s++) //iterating through all subsets in lexicographical order
for (int a = 0; a < N; a++) {
int r = res[s][a];
for (int v = 0; v < N; v++) { //looking through all transitions (cities to visit next)
if (s & (1<<v)) continue; //we cannot visit cities that are already visited
int ns = s  (1<<v); //perform transition
int na = v;
int nr = r + matr[a][v]; //by adding edge (a  v) distance
if (res[ns][na] > nr) //relax result for state (ns,na) with nr
res[ns][na] = nr;
}
}
int answer = 1000000000; //get TSP answer
for (int a = 0; a < N; a++)
answer = min(answer, res[(1<<N)1][a] + matr[a][0]);
Often in DP over subsets you have to iterate through all subsets or supersets of a given set s. The bruteforce implementation will require O(4^N) time for the whole DP, but it can be easily optimized to take O(3^N). Please read recipe "Iterating Over All Subsets of a Set".
Substrings of a given string
There is a fixed string or a fixed segment. According to the problem definition, it can be broken into two pieces, then each of pieces can be again divided into two pieces and so forth until we get unitlength strings. And by doing this we need to achieve some goal.
Classical example of DP over substrings is contextfree grammar parsing algorithm. Problems which involve putting parentheses to arithmetic expression and problems that ask to optimize the overall cost of recursive breaking are often solved by DP over substrings. In this case there are two special parameters L and R which represent indices of left and right borders of a given substring. There can be some additional parameters, we denote them as "a". So each state is defined by (L,R,a). To calculate answer for each state, all the ways to divide substring into two pieces are considered. Because of it, states must be iterated through in order or nondecreasing length. Here is the scheme of DP over substrings (without additional parameters):
res[N+1][N+1]; //first: L, second: R
for (int s = 0; s<=N; s++) //iterate size(length) of substring
for (int L = 0; L+s<=N; L++) { //iterate left border index
int R = L + s; //right border index is clear
if (s <= 1) {
res[L][R] = DPBase(L, R); //base of DP  no division
continue;
}
tres = ???;
for (int M = L+1; M<=R1; M++) //iterate through all divisions
tres = DPInduction(tres, res[L][M], res[M][R]);
res[L][R] = tres;
}
answer = DPAnswer(res[0][N]);


Subsets of a given set
The problems of this type has some set X. The number of elements in this set is small: less than 20. The idea of DP solution is to consider all subsets of X as state domain. Often there are additional parameters. So generally we have state domain in form (s,a) where s is a subset of X and "a" represents additional parameters.
Consider TSP problem as an example. The set of cities X={0, 1, 2, ..., N1} is used here. State domain will have two parameters: s and a. The state (s,a)>R means that R is the shortest path from city 0 to city "a" which goes through all the vertices from subset s exactly once. The transition is simply adding one city v to the end of path: (s,a)>R turns into (s+{v},v)>R + M[a,v]. Here M[i,j] is distance between ith and jth city. Any hamiltonian cycle is a path which goes through each vertex exactly once plus the edge which closes the cycle, so the answer for TSP problem can be computed as min(R[X,a]+M[a,0]) among all vertices "a".
It is very convenient to encode subsets with binary numbers. Look this recipe for detailed explanation.
The state domain of DP over subsets is usually ordered by set inclusion. Each forward transition adds some elements to the current subset, but does not subtract any. So result for each state (s,a) depends only on the results of states (t,b) where t is subset of s. If state domain is ordered like this, then we can iterate through subsets in lexicographical order of binary masks. Since subsets are usually represented with binary integers, we can iterate through all subsets by iterating through all integers from 0 to 2^N  1. For example in TSP problem solution looks like:
int res[1<<N][N];
memset(res, 63, sizeof(res)); //filling results with positive infinity
res[1<<0][0] = 0; //DP base
for (int s = 0; s < (1<<N); s++) //iterating through all subsets in lexicographical order
for (int a = 0; a < N; a++) {
int r = res[s][a];
for (int v = 0; v < N; v++) { //looking through all transitions (cities to visit next)
if (s & (1<<v)) continue; //we cannot visit cities that are already visited
int ns = s  (1<<v); //perform transition
int na = v;
int nr = r + matr[a][v]; //by adding edge (a  v) distance
if (res[ns][na] > nr) //relax result for state (ns,na) with nr
res[ns][na] = nr;
}
}
int answer = 1000000000; //get TSP answer
for (int a = 0; a < N; a++)
answer = min(answer, res[(1<<N)1][a] + matr[a][0]);
Often in DP over subsets you have to iterate through all subsets or supersets of a given set s. The bruteforce implementation will require O(4^N) time for the whole DP, but it can be easily optimized to take O(3^N). Please read this recipe.
Substrings of a given string
There is a fixed string or a fixed segment. According to the problem definition, it can be broken into two pieces, then each of pieces can be again divided into two pieces and so forth until we get unitlength strings. And by doing this we need to achieve some goal.
Classical example of DP over substrings is contextfree grammar parsing algorithm. Problems which involve putting parentheses to arithmetic expression and problems that ask to optimize the overall cost of recursive breaking are often solved by DP over substrings. In this case there are two special parameters L and R which represent indices of left and right borders of a given substring. There can be some additional parameters, we denote them as "a". So each state is defined by (L,R,a). To calculate answer for each state, all the ways to divide substring into two pieces are considered. Because of it, states must be iterated through in order or nondecreasing length. Here is the scheme of DP over substrings (without additional parameters):
res[N+1][N+1]; //first: L, second: R
for (int s = 0; s<=N; s++) //iterate size(length) of substring
for (int L = 0; L+s<=N; L++) { //iterate left border index
int R = L + s; //right border index is clear
if (s <= 1) {
res[L][R] = DPBase(L, R); //base of DP  no division
continue;
}
tres = ???;
for (int M = L+1; M<=R1; M++) //iterate through all divisions
tres = DPInduction(tres, res[L][M], res[M][R]);
res[L][R] = tres;
}
answer = DPAnswer(res[0][N]);


Subsets of a given set
The problems of this type has some set X. The number of elements in this set is small: less than 20. The idea of DP solution is to consider all subsets of X as state domain. Often there are additional parameters. So generally we have state domain in form (s,a) where s is a subset of X and a represents additional parameters.
Consider TSP problem as an example. The set of cities X={0, 1, 2, ..., N1} is used here. State domain will have two parameters: s and a. The state (s,a)>R means that R is the shortest path from city 0 to city a which goes through all the vertices from subset s exactly once. The transition is simply adding one city v to the end of path: (s,a)>R turns into (s+{v},v)>R + M[a,v]. Here M[i,j] is distance between ith and jth city. Any hamiltonian cycle is a path which goes through each vertex exactly once plus the edge which closes the cycle, so the answer for TSP problem can be computed as min(R[X,a]+M[a,0]) among all vertices a.
It is very convenient to encode subsets with binary numbers. Look this recipe for detailed explanation.
The state domain of DP over subsets is usually ordered by set inclusion. Each forward transition adds some elements to the current subset, but does not subtract any. So result for each state (s,a) depends only on the results of states (t,b) where t is subset of s. If state domain is ordered like this, then we can iterate through subsets in lexicographical order of binary masks. Since subsets are usually represented with binary integers, we can iterate through all subsets by iterating through all integers from 0 to 2^N  1. For example in TSP problem solution looks like:
int res[1<<N][N];
memset(res, 63, sizeof(res)); //filling results with positive infinity
res[1<<0][0] = 0; //DP base
for (int s = 0; s < (1<<N); s++) //iterating through all subsets in lexicographical order
for (int a = 0; a < N; a++) {
int r = res[s][a];
for (int v = 0; v < N; v++) { //looking through all transitions (cities to visit next)
if (s & (1<<v)) continue; //we cannot visit cities that are already visited
int ns = s  (1<<v); //perform transition
int na = v;
int nr = r + matr[a][v]; //by adding edge (a  v) distance
if (res[ns][na] > nr) //relax result for state (ns,na) with nr
res[ns][na] = nr;
}
}
int answer = 1000000000; //get TSP answer
for (int a = 0; a < N; a++)
answer = min(answer, res[(1<<N)1][a] + matr[a][0]);
Often in DP over subsets you have to iterate through all subsets or supersets of a given set s. The bruteforce implementation will require O(4^N) time for the whole DP, but it can be easily optimized to take O(3^N). Please read this recipe.
Substrings of a given string
There is a fixed string or a fixed segment. According to the problem definition, it can be broken into two pieces, then each of pieces can be again divided into two pieces and so forth until we get unitlength strings. And by doing this we need to achieve some goal.
Classical example of DP over substrings is contextfree grammar parsing algorithm. Problems which involve putting parentheses to arithmetic expression and problems that ask to optimize the overall cost of recursive breaking are often solved by DP over substrings. In this case there are two special parameters L and R which represent indices of left and right borders of a given substring. There can be some additional parameters, we denote them as "a". So each state is defined by (L,R,a). To calculate answer for each state, all the ways to divide substring into two pieces are considered. Because of it, states must be iterated through in order or nondecreasing length. Here is the scheme of DP over substrings (without additional parameters):
res[N+1][N+1]; //first: L, second: R
for (int s = 0; s<=N; s++) //iterate size(length) of substring
for (int L = 0; L+s<=N; L++) { //iterate left border index
int R = L + s; //right border index is clear
if (s <= 1) {
res[L][R] = DPBase(L, R); //base of DP  no division
continue;
}
tres = ???;
for (int M = L+1; M<=R1; M++) //iterate through all divisions
tres = DPInduction(tres, res[L][M], res[M][R]);
res[L][R] = tres;
}
answer = DPAnswer(res[0][N]);


Subsets of a given set
The problems of this type has some set X. The number of elements in this set is small: less than 20. The idea of DP solution is to consider all subsets of X as state domain. Often there are additional parameters. So generally we have state domain in form (s,a) where s is a subset of X and a represents additional parameters.
Consider TSP problem as an example. The set of cities X={0, 1, 2, ..., N1} is used here. State domain will have two parameters: s and a. The state (s,a)>R means that R is the shortest path from city 0 to city a which goes through all the vertices from subset s exactly once. The transition is simply adding one city v to the end of path: (s,a)>R turns into (s+{v},v)>R + M[a,v]. Here M[i,j] is distance between ith and jth city. Any hamiltonian cycle is a path which goes through each vertex exactly once plus the edge which closes the cycle, so the answer for TSP problem can be computed as min(R[X,a]+M[a,0]) among all vertices a.
It is very convenient to encode subsets with binary numbers. Look this recipe for detailed explanation.
The state domain of DP over subsets is usually ordered by set inclusion. Each forward transition adds some elements to the current subset, but does not subtract any. So result for each state (s,a) depends only on the results of states (t,b) where t is subset of s. If state domain is ordered like this, then we can iterate through subsets in lexicographical order of binary masks. Since subsets are usually represented with binary integers, we can iterate through all subsets by iterating through all integers from 0 to 2^N  1. For example in TSP problem solution looks like:
int res[1<<N][N];
memset(res, 63, sizeof(res)); //filling results with positive infinity
res[1<<0][0] = 0; //DP base
for (int s = 0; s < (1<<N); s++) //iterating through all subsets in lexicographical order
for (int a = 0; a < N; a++) {
int r = res[s][a];
for (int v = 0; v < N; v++) { //looking through all transitions (cities to visit next)
if (s & (1<<v)) continue; //we cannot visit cities that are already visited
int ns = s  (1<<v); //perform transition
int na = v;
int nr = r + matr[a][v]; //by adding edge (a  v) distance
if (res[ns][na] > nr) //relax result for state (ns,na) with nr
res[ns][na] = nr;
}
}
int answer = 1000000000; //get TSP answer
for (int a = 0; a < N; a++)
answer = min(answer, res[(1<<N)1][a] + matr[a][0]);
Often in DP over subsets you have to iterate through all subsets or supersets of a given set s. The bruteforce implementation will require O(4^N) time for the whole DP, but it can be easily optimized to take O(3^N). Please read this recipe.
Substrings of a given string
There is a fixed string or a fixed segment. According to the problem definition, it can be broken into two pieces, then each of pieces can be again divided into two pieces and so forth until we get unitlength strings. And by doing this we need to achieve some goal.
Classical example of DP over substrings is contextfree grammar parsing algorithm. Problems which involve putting parentheses to arithmetic expression and problems that ask to optimize the overall cost of recursive breaking are often solved by DP over substrings. In this case there are two special parameters L and R which represent indices of left and right borders of a given substring. So each state is defined by (L,R,a). To calculate answer for each state, all the ways to divide substring into two pieces are considered. Because of it, states must be iterated through in order or nondecreasing length. Here is the scheme of DP over substrings (without additional parameters):
res[N+1][N+1]; //first: L, second: R
for (int s = 0; s<=N; s++) //iterate size(length) of substring
for (int L = 0; L+s<=N; L++) { //iterate left border index
int R = L + s; //right border index is clear
if (s <= 1) {
res[L][R] = DPBase(L, R); //base of DP  no division
continue;
}
tres = ???;
for (int M = L+1; M<=R1; M++) //iterate through all divisions
tres = DPInduction(tres, res[L][M], res[M][R]);
res[L][R] = tres;
}
answer = DPAnswer(res[0][N]);


Subsets of a given set
The problems of this type has some set X. The number of elements in this set is small: less than 20. The idea of DP solution is to consider all subsets of X as state domain. Often there are additional parameters. So generally we have state domain in form (s,a) where s is a subset of X and a represents additional parameters.
Consider TSP problem as an example. The set of cities X={0, 1, 2, ..., N1} is used here. State domain will have two parameters: s and a. The state (s,a)>R means that R is the shortest path from city 0 to city a which goes through all the vertices from subset s exactly once. The transition is simply adding one city v to the end of path: (s,a)>R turns into (s+{v},v)>R + M[a,v]. Here M[i,j] is distance between ith and jth city. Any hamiltonian cycle is a path which goes through each vertex exactly once plus the edge which closes the cycle, so the answer for TSP problem can be computed as min(R[X,a]+M[a,0]) among all vertices a.
It is very convenient to encode subsets with binary numbers. Look this recipe for detailed explanation.
The state domain of DP over subsets is usually ordered by set inclusion. Each forward transition adds some elements to the current subset, but does not subtract any. So result for each state (s,a) depends only on the results of states (t,b) where t is subset of s. If state domain is ordered like this, then we can iterate through subsets in lexicographical order of binary masks. Since subsets are usually represented with binary integers, we can iterate through all subsets by iterating through all integers from 0 to 2^N  1. For example in TSP problem solution looks like:
int res[1<<N][N];
memset(res, 63, sizeof(res)); //filling results with positive infinity
res[1<<0][0] = 0; //DP base
for (int s = 0; s < (1<<N); s++) //iterating through all subsets in lexicographical order
for (int a = 0; a < N; a++) {
int r = res[s][a];
for (int v = 0; v < N; v++) { //looking through all transitions (cities to visit next)
if (s & (1<<v)) continue; //we cannot visit cities that are already visited
int ns = s  (1<<v); //perform transition
int na = v;
int nr = r + matr[a][v]; //by adding edge (a  v) distance
if (res[ns][na] > nr) //relax result for state (ns,na) with nr
res[ns][na] = nr;
}
}
int answer = 1000000000; //get TSP answer
for (int a = 0; a < N; a++)
answer = min(answer, res[(1<<N)1][a] + matr[a][0]);
Often in DP over subsets you have to iterate through all subsets or supersets of a given set s. The bruteforce implementation will require O(4^N) time for the whole DP, but it can be easily optimized to take O(3^N). Please read this recipe.
Substrings of a given string
There is a fixed string or a fixed segment. According to the problem definition, it can be broken into two pieces, then each of pieces can be again divided into two pieces and so forth until we get unitlength strings. And by doing this we need to achieve some goal.
Classical example of DP over substrings is contextfree grammar parsing algorithm. Problems which involve putting parentheses to arithmetic expression and problems that ask to optimize the overall cost of recursive breaking are often solved by DP over substrings. In this case there are two special parameters L and R which represent indices of left and right borders of a given substring. So each state is defined by (L,R,a). To calculate answer for each state, all the ways to divide substring into two pieces are considered. Because of it, states must be iterated through in order or nondecreasing length. Here is the scheme of DP over substrings (without additional parameters):
res[N+1][N+1]; //first: L, second: R
for (int s = 0; s<=N; s++) //iterate size(length) of substring
for (int L = 0; L+s<=N; L++) { //iterate left border index
int R = L + s; //right border index is clear
if (s <= 1) {
res[L][R] = DPBase(L, R); //base of DP  no division
continue;
}
tres = ?;
for (int M = L+1; M<=R1; M++) //iterate through all divisions
tres = DPInduction(tres, res[L][M], res[M][R]);
res[L][R] = tres;
}
answer = DPAnswer(res[0][N]);


Subsets of a given set
The problems of this type has some set X. The number of elements in this set is small: less than 20. The idea of DP solution is to consider all subsets of X as state domain. Often there are additional parameters. So generally we have state domain in form (s,a) where s is a subset of X and a represents additional parameters.
Consider TSP problem as an example. The set of cities X={0, 1, 2, ..., N1} is used here. State domain will have two parameters: s and a. The state (s,a)>R means that R is the shortest path from city 0 to city a which goes through all the vertices from subset s exactly once. The transition is simply adding one city v to the end of path: (s,a)>R turns into (s+{v},v)>R + M[a,v]. The answer for TSP problem can be computed as min(R[X,a]+M[a,0]) among all vertices a.
It is very convenient to encode subsets with binary numbers. Look this recipe for detailed explanation.
The state domain of DP over subsets is usually ordered by set inclusion. Each forward transition adds some elements to the current subset, but does not subtract any. So result for each state (s,a) depends only on the results of states (t,b) where t is subset of s. If state domain is ordered like this, then we can iterate through subsets in lexicographical order of binary masks. Since subsets are usually represented with binary integers, we can iterate through all subsets by iterating through all integers from 0 to 2^N  1. For example in TSP problem solution looks like:
int res[1<<N][N];
memset(res, 63, sizeof(res)); //filling results with positive infinity
res[1<<0][0] = 0; //DP base
for (int s = 0; s < (1<<N); s++) //iterating through all subsets in lexicographical order
for (int a = 0; a < N; a++) {
int r = res[s][a];
for (int v = 0; v < N; v++) { //looking through all transitions (cities to visit next)
if (s & (1<<v)) continue; //we cannot visit cities that are already visited
int ns = s  (1<<v); //perform transition
int na = v;
int nr = r + matr[a][v];
if (res[ns][na] > nr) //relax result for state (ns,na) with nr
res[ns][na] = nr;
}
}
int answer = 1000000000; //get TSP answer
for (int a = 0; a < N; a++)
answer = min(answer, res[(1<<N)1][a] + matr[a][0]);
Often in DP over subsets you have to iterate through all subsets or supersets of a given set s. The bruteforce implementation will require O(4^N) time for the whole DP, but it can be easily optimized to take O(3^N). Please read this recipe.
Substrings of a given string
There is a fixed string or a fixed segment. According to the problem definition, it can be broken into two pieces, then each of pieces can be again divided into two pieces and so forth until we get unitlength strings. And by doing this we need to achieve some goal.
Classical example of DP over substrings is contextfree grammar parsing algorithm. Problems which involve putting parentheses to arithmetic expression and problems that ask to optimize the overall cost of recursive breaking are often solved by DP over substrings. In this case there are two special parameters l and r which represent indices of left and right borders of a given substring. So each state is defined by (l,r,a). To calculate answer for each state, all the ways to divide substring into two pieces are considered. Because of it, states must be iterated through in order or nondecreasing length. Here is the scheme of DP over substrings (without additional parameters):
res[N+1][N+1]; //first: l, second: r
for (int s = 0; s<=N; s++) //iterate size(length) of substring
for (int l = 0; l+s<=N; l++) { //iterate left border index
int r = l + s; //right border index is clear
if (s <= 1) {
res[l][r] = DPBase(l, r); //base of DP  no division
continue;
}
tres = ?;
for (int m = l+1; m<=r1; m++) //iterate through all divisions
tres = DPInduction(tres, res[l][m], res[m][r]);
res[l][r] = tres;
}
answer = DPAnswer(res[0][N]);

