 # Plz help solving Dish Distribution using DP

Dear codemates i am noob in solving DP problems. I tried to solve the above problem but failed. Can anyone explain how it works and the solving strategy.

This was the Easy problem for this month. The problem is a standard combinatorics problem which asks us to find the number of solutions possible for:

x1 + x2 + x3 + … + xm = n
with the constraints ai<=xi<=bi

Though the problem can be solved using combinatorics, the constraints and the time limit of the problem allow a simple O(n3) dp solution to pass. The recurrence is straight-forward. Let dp[x][y] denote the number of ways of preparing y dishes by the first x cooks. Clearly, our answer will be dp[m][n]. The recurrence is as follows:

dp[i][j]=?dp[i-1][j-k] where x[i]<=k<=y[i]

A lot of people had a problem passing the time limit with a recursive solution. It’s always better to write an iterative code for your solution, especially if the recurrence is simple.

can u exp. this with abv example?

did you read the contest editorial for that specific problem ?

2 Likes

yea…but i dnt understand clearly …thats wat i ask to explain with a specific case

what specific thing didn’t you understand ?

1 Like

can u explain how it contruct with 1, 3 2 ,0 3 ,1 3

Ok I am a beginner in dp as well.Can you illustrate on how you arrived at this recurrence. A little more illustration will help understand.