## Dynamic Programming

I have a problem that I don't know how to start.

An oil company has 6 units of money available for exploration of three sites. If oil is present at a site, the probability of finding it is a function of the funds allocated for exploring the site, as shown in the table.

Units allocated

-------0- 1- 2 -3 4 -5 -6
-----------------------------------
Site 1: 0 .1 .2 .3 .4 .5 .7
Site 2: 0 .1 .3 .5 .6 .7 .8
Site 3: 0 -0 .2 .4 .6 .8 .9

The probably that oil exists at the sites 1, 2, and 3, are 0.2, 0.4, and 0.5, respectively. Using a dynamic-programming approach, determine how much money should be allocated to exploration of each site to maximize the probability of discovering oil. Treat this as a three-stage process, in which stage j is allocation of money to site j. Use the following definitions:

$x_{j}$ = number of units of money allocated to site j

$P_{j} (x_{j})$ = probability of finding oil at site j when $x_{j}$ is allocated, given that oil exists

$q_{j}$ = probability that oil exists at site j

u = number of units of money remaining

$m_{j} (u)$= minimum probability of not finding oil, given that the company is in state u at the start of stage j