Dynamic Programming: Largest Number of Dams that can be built

Question

Because of the recent droughts, $N$ proposals have been made to dam the Murray river. The $i$-th proposal asks to place a dam $x_i$ meters from the head of the river (i.e., from the source of the river) and requires that there is not another dam within $r_i$ metres (upstream or downstream). What is the largest number of dams that can be built? You may assume that $x_i < x_{i+1}$.

Answer 1

I would create a digraph denoted by $G$ to model this problem in the following way. Let the dam proposal which is $x_i$ metres away from the river source be denoted by $P_i$. The nodes of the graph will correspond to the $P_i$ proposals. The node corresponding to $P_i$ is denoted by $v_i$. We will have two additional nodes, $s$ and $t$, where $s$ corresponds to the source of the river. Regarding the edges:

1. there is directed edge from $s$ to the node of $v_i$, iff the distance between the source and $P_i$ is greater, than $r_i$ for all $1 \leq i \leq N$
2. there is a directed edge from $v_i$ to $v_j$ iff, $i < j$ and the distance between $P_i$ and $P_j$ is greater, than $max(r_i, r_j)$ for all $1 \leq i < j \leq N$
3. There is a directed edge from $v_i$ to $t$ for all $1 \leq i \leq N$

Note, that by the construction of this graph, a series of dams $P_{k_1},...,P_{k_r}$ can be built iff the directed path $s,v_{k_1},...,v_{k_r},t$ is in $G$. Therefore the largest number of dams can be built equals to the longest directed path from $s$ to $t$, minus 2 ($s$ and $t$ won't get built), where the length of a path is the number of vertices contained by this path.
As $G$ does not contain any directed cycle (again by the construction of $G$), one can apply this well-known dynamic programming based algorithm.
Please note, that you can rephrase my argument to a clear dynamic programming approach if you want. However, modeling your problem using a digraph is more clear and easier to understand in my opinion.

Edit 1: Hint for the clear dynamic programming approach

If you want a direct approach, consider the problem of finding the largest number of dams can be built, where the furthest dam from the source being built is $P_k$ for some fixed $k$. If you know the answer for all $1 \leq i < k$, how would you find the optimum for $k$?