The problem Hills states that we have to build k houses where each house must be strictly greater than its neighbours.

Here is one accepted solution.

I am not able to get transitions. if dp[x][y][z] denotes minimum cost to build y houses upto index x, and z tells whether we are going to build house on index x or not.

Now if z == 0, it means we are not gonna build house at current index x.

```
if (z==0)
{
int cost=0;
if (a[x-1]>=a[x]) cost+=(a[x-1]-a[x]+1);
if (a[x+1]>=a[x]) cost+=(a[x+1]-a[x]+1);
dp[x][y][z]=min(caldp(x+1,y,0),caldp(x+2,y-1,1)+cost);
}
```

Then according to above transition.My doubt is, why are we calculating caldp(x+2,y-1,1). since it means that we made a house at index x with some cost and can't build at index x+1 and recurring for x+2. But z = 0 means we are not building any house at index x.

&&&

```
if(z!=0)
{
int cost=0;
if (min(a[x-2]-1,a[x-1])>=a[x]) cost+=(min(a[x-2]-1,a[x-1])-a[x]+1);
if (a[x+1]>=a[x]) cost+=(a[x+1]-a[x]+1);
dp[x][y][z]=min(caldp(x+1,y,0),caldp(x+2,y-1,1)+cost);
}
```

And if z != 0, it means we are gonna build house at index x, why the cost will not be only (a[x-1]-a[x]+1) + (a[x+1]-a[x]+1). Why in the above equation there is a comparision between min(a[x-2]-1,a[x-1] >= a[x]). again my doubt is if we build a house at index at then we have to lower hills of index x-1 and x+1, why we are taking index x-2 in consideration.

Please help. Stuck in this problem since 2 days, trying to understand, but not getting clear picture. Thanks.

Thank you for trying to interpret my code.

z in dp[x][y][z] is equal to 0 if a[x-1] is not changed, and is equal to 1 if a[x-1] is changed according to the height of a[x-2]

Therefore,

Thanks a lot. I understood it now. I was misinterpreting dp definition. Basically if previous height is not change we can either eastablish hill on current x or don't. similarly if prev. height is change and if we establish hill then we need to consider x -2 index also.

Thanks. its very clear now.