Thinking in Dynamic Programming

[smilitude]

My vision to dynamic programming is not clear yet. To me dynamic programming is just saving the results of subproblems so that for solving the main problem, we dont need to recall that subproblems more than once. But this thinking is precisely 'memoization'. The most problems that i encounter are mainly solved in a different manner. They are divided into two phases like phase i and phase j, and phase i is related with phase j such you need to solve phase i in order to solve phase j.

Say, a simple problem. You are given a set of numbers A, you are given a sum M, if i have to find 'total possible ways' to form M by using members of A (as many time, as we wish), how will you develop its solution ? I cannot define it in phases, nor i can see any subproblem here!

I have seen some good problems' dp solution from my friends, whenever i faced a dp solution after thinking about the problem, DP seemed like magic to me. But i couldnt be the magician ...

[mf]

Say, a simple problem. You are given a set of numbers A, you are given a sum M, if i have to find 'total possible ways' to form M by using members of A (as many time, as we wish), how will you develop its solution ?

That's a coin-change problem. Let A={a1,a2,...,a_n}, where all a_i>0, and define f(k, s) = number of ways to make sum s using only numbers from {a1,...,a_k}.

How to compute f(k, s)? Let's start by asking: is there a term a_k in the sum? If there isn't one, then the number of sums is just f(k-1, s); otherwise it is f(k, s-a_k), and hence the recurrence:

f(k, s) = f(k-1, s) + f(k, s-a_k).
A special case: if s<a_k, then f(k,s) = f(k-1,s).

They are divided into two phases like phase i and phase j, and phase i is related with phase j such you need to solve phase i in order to solve phase j.

Phase -- it's just an additional variable in dp.

For example you can implement the above solution with a single table a[0..M]: make a loop on k; at the k-th iteration maintain the invariant: a[s]=f(k, s).
Here k is probably what you call a 'phase', but actually it's just another variable in dp.

[smilitude]

thanks!
I solved that problem thinking like this (which is same to your recurrence)
let f[x] be the ways of finding sum of x, then after some observations it comes like

f[x] = f[x-element 1] + f[x - element 2] + .... .... .... +f[x - element n];

Then we need to put two loops thats all.
I think i understand dp little now... mf, can you give me some easy dp problems for me ? you know a kid needs to walk step by step ...

thanks again mf!

[jjtse]

hey, congratulations for solving the coin change problem. Can you show me how you build your table? Because I can't seem to find the relationship between the coins and the sum value.

[smilitude]

Code: Select all

 f[0]=1;
    for(j=0;j<V;j++) {
        for(i=1;i<=N;i++) {
            if(i<elem[j]) continue;
            f[i]+=f[i-elem[j]];
        }
    }

Here V is the number of elements, and N is the sum;

[jjtse]

I actually found a similar piece of code in several places. But I don't understand what its trying to do.

Can you explain it in words?
For example:

for 1,2,3,4, the number of combinations is trivially 1, because only pennies can make up that value.


For 5, the number of combinations becomes 2: using pennies only, or using nickels only


for 10, what's the reasoning in constructing 10? Is it the number of combinations for using pennies + num of combo for using nickels + num of combo for using dimes = 4?

[smilitude]

sorry jitse, i had exams.

i dont understand penny-nickels well, so plz dont mind and let me introduce this problem with easier statement :: like we got 3 coins with values 1,2,5 and we got to find the maximum ways to build up the sum 10.

if you try to build the table by hand, you'll see for only one coin, let it be 1, all the sums upto 10 can be made only in one way. Now lets add coin 2 in our table, it wont change the values smaller than 2, but for the values greater than 2 we are certainly getting some new more ways. but now the question comes, how much more ways, well for 3, it seems like we had 1 way, now we as can add 2, to some other values, so the increment would be sum[3-2]=sum[1](when we are using 2, we got more ways what built the n-2, and add that value to the sum); thats why we add +=sum[i-elem[j]; then working with 2, lets add 3 now in our coin list, when this would finish, our work will be done.

i have found, that its extremely useful to build the table by hand, for first few steps... while you are building the table, may be you'll find the relation.

Hope you understood...

[jjtse]

hey smilitude, thanks for the response. I had exams too. I'm actually going to be a little busy until the weekend. I'll check it out again during the weekeend and tell you how everything went.

[yogeshgo05]

hi guys ..
even i m learning dp ....
its very challenging dude..
smilitude ,...the code u gave for coin exchange is standard i guess.
i m having problems solving problem 674.. coin exchange i get tle...
is there better optimized code for solving this problem.....plz help after ur exams..

[smilitude]

its okay yogi!
i just got hand on dp... i was trying to understand it last a whole year!! I looked back at my codes, and found this is the one i wrote for 674 long time ago...

Code: Select all

  max = 5;
  ways[0] = 1;
  for (i=0; i<max; i++) {
    for (j=coin[i]; j<=7489; j++)
      ways[j] += ways[j-coin[i]];
  }
  while(scanf("%d",&n)==1) {
	  printf("%ld\n",ways[n]);
  }

Hmm... that time when i coded it i didnt do it totally by myself... i took help from a friend as far as i can remember.

[jjtse]

dude! I just solved problem 624, which was a twisted version of the knapsack problem. I'm going to retry solving the coin change problem. Maybe now I can get it to work.

[zero_cool]

Code: Select all

 f[0]=1;
    for(j=0;j<V;j++) {
        for(i=1;i<=N;i++) {
            if(i<elem[j]) continue;
            f[i]+=f[i-elem[j]];
        }
    }

Here V is the number of elements, and N is the sum;

I use the same code but it doesn't work for some kind of weird coin system example: {11...26}. Is there any other dp to compute the number of ways?

Forget it. It works. I use the wrong data type.

[jjtse]

Oh, by the way, I solvd the coin change problem as welll. Shortly I will solve the cutting sticks problem, which is also dynamic programming. I had my professor help me on that one.