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.

thanks in advance

did you read the contest editorial for that specific problem ?


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

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?

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.