# UVa 10874

## Summary

This is a very simple Dynamic Programming problem.

## Explanation

Use the following recurrence relation

${\displaystyle best(d,i)=\min((best(d+1,0)+|value[d][0]-value[d-1][i]|+dist(d)),(best(d+1,1)+|value[d][1]-value[d-1][i]|+dist(d)))+1}$

${\displaystyle dist(d)=(value[d][1]-value[d][0])}$

Base Case:

${\displaystyle best(n,i)=n-value[d-1][i]-1}$

Here we came from the ith point in depth d and now we have two choices for going to depth d+1. So, we'll pick the minimum path among them. Cost calculation of each step is a simple math.

Also, need Memoization of size N x 2.

## Notes

• You need to consider 1 for the down step.

```5
4 4
3 5
1 1
2 3
2 2
9
6 6
2 7
4 8
3 4
5 8
3 5
6 7
1 2
5 6
10
2 8
3 7
5 8
2 6
5 7
6 9
5 10
4 4
7 8
2 7
0
```

```18
56
66
```