You are not logged in. Please login at to post your questions!


Help required in Simple DP problem

Problem Link

Can anyone help me with this solution First tell what should I do to get 60 points and then 100 points.

I have got 20 points in this solution. I thought I would get TLE in rest of subtask but its giving WA. Can anyone tell me in which case I am getting WA

asked 20 May '15, 20:32

ankurverma1994's gravatar image

accept rate: 8%

converted to question 20 May '15, 20:43

Your dp equation needs to be modified. You wrote dp[j][k] = dp[j - 1][k] + min(disc, min). I assume dp[j][k] denotes the total cost of j items with last item bought in the kth house. Then min(disc, min) is wrong. It should be only disc. And it it not necessary that he always gets a discount. It is also possible that dp[j][k] = dp[j - 1][h] + price[j][k] where h is anything from 1 to m.

So your final dp equation should be

dp[j][k] = min(dp[j - 1][k] + disc, val + price[j][k]) where val = min of all (dp[j - 1][h]) for h in range (1, m)


answered 21 May '15, 10:23

loch_ish's gravatar image

accept rate: 20%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • 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:


question asked: 20 May '15, 20:32

question was seen: 668 times

last updated: 21 May '15, 15:18