mokoto's blog

By mokoto, history, 4 years ago, In English

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.

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

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,

  • In the first case (z==0), the height of a[x-1] is a[x-1]. The additional cost to make a[x-1] lower than a[x] is (a[x-1]-a[x]+1)
  • In the second case (z==1), the height of a[x-1] is lower than a[x-2] and is equal to min(a[x-2]-1,a[x-1]). The additional cost to make a[x-1] lower than a[x] is (min(a[x-2]-1,a[x-1])-a[x]+1)