Dynamic Programming

[rampage1]

I am just unable to get the hang of dp. I know what I've to do but am just unable to implement it.
E.g this practice problem from 'Codechef'
http://www.codechef.com/problems/MIXTURES/

If i consider the min smoke for mixtures i to j as m[i,j]

then for k<- i to j
m[i,j]=min(m[i,k]+m[k+1,j]+cost of mixing the resulting mixtures)

Is this correct?

and how do I keep updating the colors of the mixtures for diff k and then revert back to original for the next k?

[D80DSL3A]

Interesting problem! I have this so far. It appears to work for any given mixing order. User gives which vials to mix in each mixing stage and program gives the smoke produced and the new list of colors for the next mixing stage. Totals are given after the last set of vial indexes is given.
Can this be used to help find the mixing order producing the least smoke? That would be the next task.

// Harry Potter potion mixing problem
// Takes # of vials = N
// Takes list of color values(0-99) for the vials
//Prompts for vial indexes to mix for each of the N-2 mixing stages
//Reports smoke produced and new color array on each stage
//Reports total smoke at end

#include <iostream>// for use of cin, cout
using namespace std;

int Mix(int a, int b, int n, int* c)// must give a<b and b < N
{
	int amt = c[a]*c[b];// retVal is amount of smoke produced

	c[a] = ( c[a] + c[b] )%100;// new color for mixed powders
	for(int j=b; j<(n-1); j++)
		c[j] = c[j+1];// cycle array entries to front

	return(amt);
}// end of Mix()

int main()
{	
		
	int N = 1;// # 0f vials
	int* color;// array name

	int Smoke = 0;// total smoke produced by mixing
	int SmOne = 0;// smoke from single mix
	int a=1, b=2;// vail indices for mix

	char repeat = 'n';
		
	do// until user is done
	{	
		
		cout << "Enter # of vails: " ;
		cin >> N;
		color = new int[N];
		
		cout << "Enter color (0-99) for each vial " << endl;
		for(int j=0; j<N; j++)
		{
			cout << "color " << j << " :";
			cin >> color[j];
		}

		cout << "Give vial indices for the " << N-2 <<" mixing stages " << endl;
		for(int n=(N-1); n>1; n--)// for each mixing stage except last
		{
			cout << endl << "vial1 index: ";
			cin >> a;
			cout << "vial2 index: ";
			cin >> b;
			SmOne = Mix(a,b,N,color);
			Smoke += SmOne;
			cout << "Smoke from mix = " << SmOne << endl;// color array now changed
			cout << "New colors are: ";
			for(int j=0; j<n; j++)
				cout << color[j] << " ";
		}
		SmOne = Mix(0,1,2,color);// final mixing stage
		Smoke += SmOne;
		cout << endl << "Final Mix smoke = " << SmOne << endl;
		cout << "Final color = " << color[0] << endl;
		cout << "Total smoke is = " << Smoke << endl;

		cout << endl << "repeat (y/n)?:" << flush;
		cin >> repeat;
	}while( repeat=='y');

	delete [] color;
	return 0;
}

But, what is best method for finding minimum? Raw crunch through every case?

[ne555]

and how do I keep updating the colors of the mixtures for diff k and then revert back to original for the next k?

When mixing two mixtures of colors a and b, the resulting mixture will have the color (a+b) mod 100.
Number theory:
(a+b) mod m = (a mod m + b mod m) mod m
If you analize that, it does not mather the order of the mixing process, the resulting color will always be the same.

then for k<- i to j
m[i,j]=min(m[i,k]+m[k+1,j]+cost of mixing the resulting mixtures)

The recursion is correct.

PD: Thanks for the link, the page looks interesting