JOIN
Get Time
forums  Revision History
Search My Post History  |  My Watches  |  User Settings
Forums TopCoder Cookbook Algorithm Competitions - New Recipes Re: 2.4.? Commonly used DP state domains Revision History (1 edit)
Re: 2.4.? Commonly used DP state domains (response to post by dimkadimon)
1. The Result[i1,i2,...,ik] has nothing is common with knapsack. It is array of results for general problem with multidim-like state domain. Knapsack was an example of such a problem with dim=2.

2. I added explanation for M matrix and about the way answer is got. About M and matr - it is usual thing. Mathematics is used to short variable names (1-2 letters) whereas in programming short names is bad habbit. I have a strong feeling against naming a matrix with one letter, sorry=) By the way, didn't you notice that state result is denoted as R in text but as res in code?...

3. Changed l,m,r to L,M,R. (l+1) looks really weird=) Question mark represents something that depends on the problem. It is usually neutral element i.e. 0 in combinatoric problem, +inf in minimization problem, -inf in maximization problem. I don't want to explain it here and there may be exceptions. That's why I just put question mark. Look one of examples and you'll see 10^18 in this place.

a represents additional parameters. It must be explained somewhere in the recipe=) I added a note on this to the first place it is met.

I don't like that additional parameters are represented by letter "a". Because it is english article also... I've enclosed parameter "a" in quotes in most places in text so that the do not confuse reader.
Re: 2.4.? Commonly used DP state domains (response to post by dimkadimon)
1. The Result[i1,i2,...,ik] has nothing is common with knapsack. It is array of results for general problem with multidim-like state domain. Knapsack was an example of such a problem with dim=2.

2. I added explanation for M matrix and about the way answer is got. About M and matr - it is usual thing. Mathematics is used to short variable names (1-2 letters) whereas in programming short names is bad habbit. I have a strong feeling against naming a matrix with one letter, sorry=) By the way, didn't you notice that state result is denoted as R in text but as res in code?...

3. Changed l,m,r to L,M,R. (l+1) looks really weird=) Question mark represents something that depends on the problem. It is usually neutral element i.e. 0 in combinatoric problem, +inf in minimization problem, -inf in maximization problem. I don't want to explain it here and there may be exceptions. That's why I just put question mark. Look one of examples and you'll see 10^18 in this place.

a represents additional parameters. It must be explained somewhere in the recipe=) I added a note on this to the first place it is met.

I don't like that additional parameters are represented by letter "a". Because it is english article also... Don't know how to change that. Now A already represents size of "a" parameter range.