New Topic/Question
Reply
I have been assigned to design and implement a dynamic programming algorithm to solve the below problem and I am having trouble getting started. I know that a dynamic programming algorithm takes advantage of identical sub-sub-problems by saving the values so that it doesn't have to recompute them. I have a decent understanding of the theory behind them, but I am having trouble bridging that gap between theory and practice. I am NOT looking for you guys to solve this problem for me, but any tips that could point me in the right direction would be greatly appreciated. The problem is as follows:
Let A1, A2, ..., An be a sequence of n integers. Different parenthesizations of the expression A1 −A2 −...−An may lead to different results. For example, is we take 5, 2, 7, 3, 2 as input, some possible parenthesizations and their results are shown below:
• ((5 − 2) − ((7 − 3) − 2)) = 1
• (5 − ((2 − 7) − (3 − 2))) = 11
• (5 − (((2 − 7) − 3) − 2)) = 15
Describe a dynamic programming algorithm that finds a parenthesization of the expression A1−A2−...−An that evaluates to the maximum possible result. Analyze its time and space complexity.
1 Replies - 1647 Views - Last Post: 05 November 2010 - 02:48 PM
#1 Guest_Sean77771*
Help Designing a Dynamic Programming Algorithm
Posted 04 November 2010 - 06:44 PM
MultiQuoteReplies To: Help Designing a Dynamic Programming Algorithm
#2
mojo666
- D.I.C Addict
-
Reputation: 409
- Posts: 885
- Joined: 27-June 09
Re: Help Designing a Dynamic Programming Algorithm
Posted 05 November 2010 - 02:48 PM
I think you should ultimately define 2 functions
max(first, last)
min(first, last)
You can store the results in 2-dimensional tables where max[x][y] coresponds to the result of max(x,y).
You are calculating max(1,n)
both functions will return the nth number of the sequence if both first and last are n.
Otherwise, you will have to recurse. Since you are performing subtraction, the return value will have to look something like (leftside-rightside). Think about what must be true about leftside and rightside if the result is to be the maximum (or minimum) possible value. Hope that gets you started.
max(first, last)
min(first, last)
You can store the results in 2-dimensional tables where max[x][y] coresponds to the result of max(x,y).
You are calculating max(1,n)
both functions will return the nth number of the sequence if both first and last are n.
Otherwise, you will have to recurse. Since you are performing subtraction, the return value will have to look something like (leftside-rightside). Think about what must be true about leftside and rightside if the result is to be the maximum (or minimum) possible value. Hope that gets you started.
Was This Post Helpful?
0
Page 1 of 1
| 