×

# Plz help solving Dish Distribution using DP

 0 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. http://www.codechef.com/OCT11/problems/DISHDIS thanks in advance asked 13 Apr '12, 13:41 2★rijin 15●1●1●2 accept rate: 0% 560●10●19●24 2 did you read the contest editorial for that specific problem ? (14 Apr '12, 03:36) yea...but i dnt understand clearly ....thats wat i ask to explain with a specific case (21 Apr '12, 13:59) rijin2★ 1 what specific thing didn't you understand ? (21 Apr '12, 22:21) can u explain how it contruct with 1, 3 2 ,0 3 ,1 3 (29 Apr '12, 15:02) rijin2★

 0 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? answered 15 May '12, 19:08 2★rijin 15●1●1●2 accept rate: 0% 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. (23 Jun '12, 19:36)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×2,033
×4

question asked: 13 Apr '12, 13:41

question was seen: 1,751 times

last updated: 23 Jun '12, 19:36