Re: [algogeeks] Re: Dynamic programming question
The first problem I mentioned is a similar problem. but the second one seems to be little difficult. where additional path we could go is up. - Azhar. On Thu, Dec 15, 2011 at 10:17 PM, Dheeraj Jain dheerajj...@gmail.comwrote: http://www.geeksforgeeks.org/archives/14943 is a very similar problem. On Thu, Dec 15, 2011 at 1:12 PM, WgpShashank shashank7andr...@gmail.comwrote: @Azhar , also for 1st question u r trying Array DS will suffices. Its Standard Coin Change Problem , u need to solve subproblem 1st , store it in extra array to avoid recalculation , if u are able to produce the sum less given sum then u can use same approach to reach desired sum . it uses the memozation (DP) approach solve efficiently . hope it help. Thanks Shashank Mani CSE, BIT Mesra http://shashank7s.blogspot.com/ -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/N3nEi3dNwR0J. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Dynamic programming question
http://www.geeksforgeeks.org/archives/14943 is a very similar problem. On Thu, Dec 15, 2011 at 1:12 PM, WgpShashank shashank7andr...@gmail.comwrote: @Azhar , also for 1st question u r trying Array DS will suffices. Its Standard Coin Change Problem , u need to solve subproblem 1st , store it in extra array to avoid recalculation , if u are able to produce the sum less given sum then u can use same approach to reach desired sum . it uses the memozation (DP) approach solve efficiently . hope it help. Thanks Shashank Mani CSE, BIT Mesra http://shashank7s.blogspot.com/ -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/N3nEi3dNwR0J. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Dynamic programming question
We need not necessarily pick the apple. We need to suggest a way that could have maximum apples and path need not be longest. Another person will follow our path and pick the apples. we can start from specified (i,j) and have to reach specified (i, n) traversing either top, right, down(not left). Can greedy approach work if we take a graph and try to implement shortest path algorithm(in this case max apples) from (i, j) to (i,n)? - Azhar. On Wed, Dec 14, 2011 at 6:07 PM, Gene gene.ress...@gmail.com wrote: Longest path won't work so well because it will return infinity if a path contains a positive cycle, which doesn't apply here because once you pick up an apple, it's gone. On Dec 13, 7:17 am, vikas vikas.rastogi2...@gmail.com wrote: Graph take up, right and bottom as nodes connected to current and do find max path. On Dec 13, 3:44 pm, Azhar Hussain azhar...@gmail.com wrote: We have apples arranged in a mxn matrix. We start from the upper left corner and have to reach bottom right corner with maximum apples. We can only move either down or right. Now if we can start any where in the matrix and have to reach anywhere on the right(reach n column). We can either up, down, right(but not left). We have to collect maximum apples from a given location. I am trying to solve problem. solution for the first one is given athttp://community.topcoder.com/tc?module=Staticd1=tutorialsd2=dynProg. What data structure would be suitable for the second problem and will dynamic programming work. Thanks in advance. Azhar. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Dynamic Programming Cormen
Reply for what? On Sat, Jul 16, 2011 at 1:07 PM, Nitish Garg nitishgarg1...@gmail.comwrote: Someone please reply. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/vBP5ZdFV9HEJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- **Regards SAGAR PAREEK COMPUTER SCIENCE AND ENGINEERING NIT ALLAHABAD -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Dynamic Programming Cormen
Because here we can not reOrder words, Greedy seems to work fine to me too, i am not able to come up with an contradictory example..will post if will get one... or post if any one can. but here http://mitpress.mit.edu/algorithms/solutions/chap15-solutions.pdfis the DP solution to the problem -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Dynamic Programming
int solve(int id) {
if(id==n)
return 0;
int d = dp[id];
if(~d) return d;
d = 0;
for(int i=id+1;in;i++) {
if(dis[i]-dis[id]=k) {
d ?= val[id] + solve(i);
}
}
return d;
}
Its O(n^2), and Juver++, is very correct.
On Wed, Jan 5, 2011 at 10:22 PM, Decipher ankurseth...@gmail.com wrote:
I think your solution will take O(n3) time , as it will require three
loops . 1st for index i , 2nd for first max and 3rd for second max .
Instead we should take :
dp[i] = max(dp[j]) + p[i] , where ji and m[i] - m[j] k . Pls
correct me if something is wrong .
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Dynamic Programming
I am telling the DP O(n^2) solution, whts wrong in it?? On Wed, Jan 5, 2011 at 10:36 PM, juver++ avpostni...@gmail.com wrote: Unfortunately, you are wrong. We need one loop for i and that is all. All other things for searching max p[j] is solved by segment tree in O(log n). -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Dynamic Programming
I was replying to the @Decipher post. Not yours. :) Your algorithm seems to be ok. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Dynamic Programming
ok :):) On Wed, Jan 5, 2011 at 10:43 PM, juver++ avpostni...@gmail.com wrote: I was replying to the @Decipher post. Not yours. :) Your algorithm seems to be ok. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Dynamic Programming
Minor fixes: i loop should be from 0 to id - 1, if you are moving from left to right. initial value of d should be the val[id] not 0. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Dynamic Programming
Sorry, disregard my first proposition about index i. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Dynamic Programming
In main just pass answerIs = max(val[0], solve(0)); On Wed, Jan 5, 2011 at 10:49 PM, juver++ avpostni...@gmail.com wrote: Sorry, disregard my first proposition about index i. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
