JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat  | Threaded  | Tree Previous Thread  |  Next Thread Forums TopCoder Cookbook Algorithm Competitions - New Recipes 2.4.? Commonly used DP state domains
 2.4.? Commonly used DP state domains | Reply Problem:The most creative part of inventing dynamic programming solution is defining recurrent relations. The recurrent relations consist of two parts: state domain and transitions. State domain is a set of states (subproblems) in dynamic programming. For each state the subresult will be calculated eventually. Transitions are the relations between different states which help calculate the subresults.This recipe covers frequently used state domain types. The general approaches of dealing with them and real SRM examples are given. Also few optimizations specific to particular domains are mentioned here.SolutionCode of DP solution usually contains an array representing subresults on the state domain. For example, classic knapsack problem solution will be like:``` int maxcost[items+1][space+1]; memset(maxcost, -63, sizeof(maxcost)); //fill with negative infinity maxcost[0][0] = 0; //base of DP for (int i = 0; imc to state (ni,nj)->nmc   ni = i + 1; //forward transition: do not add i-th item nj = j; nmc = mc; if (maxcost[ni][nj] < nmc) //relaxing result for new state maxcost[ni][nj] = nmc;   ni = i + 1; //forward transition: add i-th item nj = j + size[i]; nmc = mc + cost[i]; if (nj <= space && maxcost[ni][nj] < nmc) maxcost[ni][nj] = nmc; } int answer = -1000000000; //getting answer from state results for (j = 0; j<=space; j++) if (maxcost[items][j] > answer) answer = maxcost[items][j]; return answer; ```Here (i,j) is state of DP with result equal to maxcost[i][j]. The result here means the maximal cost of items we can get by taking some of first i items with overall size of exactly j. So the set of (i,j) pairs and concept of maxcost[i][j] here comprise a state domain. The forward transition is adding or not adding the i-th item to the set of items we have already chosen.The order of iterations through all DP states is important. The code above iterates through states with pairs (i,j) sorted lexicographically. It is correct since any transition goes from set (i,*) to set (i+1,*), so we see that i is increasing by one. Speaking in backward (recurrent) style, the result for each state (i,j) directly depends only on the results for the states (i-1,*).To determine order or iteration through states we have to define order on state domain. We say that state (i1,j1) is greater than state (i2,j2) if (i1,j1) directly or indirectly (i.e. through several other states) depends on (i2,j2). This is definition of order on the state domain used. In DP solution any state must be considered after all the lesser states. Else the solution would give incorrect result.Multidimensional arrayThe knapsack DP solution described above is an example of multidimensional array state domain (with 2 dimensions). A lot of other problems have similar state domains. Generally speaking, in this category states are represented by k parameters: (i1, i2, i3, ..., ik). So in the code we define a multidimensional array for state results like: int Result[N1][N2][N3]...[Nk]. Of course there are some transition rules (recurrent relations). These rules themselves can be complex, but the order of states is usually simple.In most cases the states can be iterated through in lexicographical order. To do this you have to ensure that if I = (i1, i2, i3, ..., ik) directly depends on J = (j1, j2, j3, ..., jk) then I is lexicographically greater that J. This can be achieved by permuting parameters (like using (j,i) instead of (i,j)) or reversing them. But it is usually easier to change the order and direction of nested loops. Here is general code of lexicographical traversion:``` for (int i1 = 0; i1 jres by performing transitions //and handle them } ```Note: changing order of DP parameters in array and order of nested loops can noticably affect performance on modern computers due to CPU cache behavior.This type of state domain is the easiest to understand and implement, that's why most DP tutorials show problems of this type. But it is not the most frequently used type of state domain in SRMs. DP over subsets is much more popular.
 Subject Author Date 2.4.? Commonly used DP state domains syg96 Jan 4, 2011 at 2:16 AM EST Re: 2.4.? Commonly used DP state domains syg96 Jan 4, 2011 at 2:16 AM EST Re: 2.4.? Commonly used DP state domains syg96 Jan 4, 2011 at 2:17 AM EST Re: 2.4.? Commonly used DP state domains syg96 Jan 4, 2011 at 2:17 AM EST Re: 2.4.? Commonly used DP state domains syg96 Jan 4, 2011 at 2:17 AM EST Re: 2.4.? Commonly used DP state domains syg96 Jan 4, 2011 at 2:18 AM EST Re: 2.4.? Commonly used DP state domains syg96 Jan 4, 2011 at 2:18 AM EST Re: 2.4.? Commonly used DP state domains syg96 Jan 4, 2011 at 2:18 AM EST Re: 2.4.? Commonly used DP state domains caustique Jan 4, 2011 at 10:53 AM EST Re: 2.4.? Commonly used DP state domains dimkadimon Jan 6, 2011 at 10:39 PM EST Re: 2.4.? Commonly used DP state domains supersmecher Jan 9, 2011 at 3:46 AM EST Re: 2.4.? Commonly used DP state domains i_want_passion Apr 11, 2013 at 6:51 PM EDT Re: 2.4.? Commonly used DP state domains akshayk0406 Feb 4, 2011 at 11:57 PM EST Re: 2.4.? Commonly used DP state domains syg96 Feb 12, 2011 at 11:35 AM EST Re: 2.4.? Commonly used DP state domains akshayk0406 Feb 13, 2011 at 6:20 AM EST Re: 2.4.? Commonly used DP state domains innocentboy2 Feb 17, 2011 at 5:28 AM EST Re: 2.4.? Commonly used DP state domains sadek_romel Oct 17, 2017 at 12:34 PM EDT Re: 2.4.? Commonly used DP state domains dimkadimon Jan 6, 2011 at 11:09 PM EST Re: 2.4.? Commonly used DP state domains dimkadimon Jan 7, 2011 at 7:18 PM EST Re: 2.4.? Commonly used DP state domains syg96 Jan 8, 2011 at 1:46 AM EST Re: 2.4.? Commonly used DP state domains dimkadimon Jan 6, 2011 at 10:44 PM EST Re: 2.4.? Commonly used DP state domains M.G.Z Feb 13, 2013 at 4:32 PM EST Re: 2.4.? Commonly used DP state domains syg96 Mar 22, 2013 at 10:58 AM EDT
 Forums TopCoder Cookbook Algorithm Competitions - New Recipes 2.4.? Commonly used DP state domains Previous Thread  |  Next Thread