Dynamic Programming help LISA- SPOJ
algorithm
Solution
Note that operations allowed are only `+` and `*` - binary operations that are strictly increasing in regard to both operands (they are positive).
Let `dp[l][r]` be the maximum outcome from substring [l,r]
Here are tips about this problem, which also apply to every dp.
1) What are base cases? (HINT: something very simple, that doesn't change its value with adding/removing brackets)
2) How do you move from bigger problem to smaller problem(s)? (HINT: you can try to find the place of last operation)
Problem
I was trying to solve this problem - http://www.spoj.pl/problems/LISA/ I thought of Greedy initially, but realized later that it wouldn't work. It seems like a DP problem. I'm not able to form the recurrence relation. I'm not able to form the recurrence relation. It's not just this problem, but I get stuck whenever I encounter a slightly difficult DP problem. I know this must be common and practice would help. But I am just moving from one problem to another without actually finding the solution. Any advise would be great, on the above problem and in general, DP encounters. Thanks a lot.