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
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.