No replies to this topic

[Sean77771]

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.