Someone please explain why do we need dynamic programming approach to solve
this? Cant we find the solution as mentioned by 'algose chase' above??
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@
int solve(int lo, int hi) { // lo = 0, and hi = length - 1 in initial pass
if(lo==hi)
return a[lo];
int &d = dp[lo][hi];
if(~d) return d; // dp array initialized with {-1}
d = -INF;
for(int i=lo;i wrote:
> thats right !
> DP must be the best approach to solve
thats right !
DP must be the best approach to solve it !
On Tue, Nov 30, 2010 at 10:40 PM, Akash Agrawal
wrote:
> In addition to these assumptions, you have also assumed that numbers are
> greater than 1 else * will lower the result.
>
> Regards,
> Akash Agrawal
> http://tech-queries.blogspot.c
In addition to these assumptions, you have also assumed that numbers are
greater than 1 else * will lower the result.
Regards,
Akash Agrawal
http://tech-queries.blogspot.com/
On Thu, Nov 25, 2010 at 11:18 AM, Algoose chase wrote:
> For this specific case since only 2 operators are used : + , *
For this specific case since only 2 operators are used : + , * and we
know that * is the operator that maximizes the value(provided both the
operands are not equal to one / none of the operand is zero and also given
that operands are +ve ).
Doing * operation as late as possible should suffice
you can use an algorithm similar to matrix chain multiplication i.e. if
dp[i][j] is the maximum value that you can get with the numbers v_i to v_j
and in order to maximize it find k that maximizes ( dp[i][k] op_k dp[k][j]
)
v_i is the ith value and op_k is the kth operator
obviously if i==j : dp
given an expression of n numbers separated by " * " and " + "
operators but the order of operations is not clear as the parenthesis
have been removed. how will i get the maximum result for this
expression.
--
You received this message because you are subscribed to the Google Groups
"Algorithm G
