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.Mydoubt it, 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.