In_The_Name_Of_Love's blog

String Problem
By In_The_Name_Of_Love, history, 6 years ago, In English

You're given String which consists of open and close bracket, numbers and question mark (?). Also you're given two integer M and N. M is number of plus (+) and N is number of minus (-). You'll have to replace question mark (?) with plus (+) or minus (-) and maximize the expression. You'll have to use exactly M plus (+) and N (-). It is guaranteed that M + N = Number of question mark(?).

1 <= Length of String <= 10000

Example : String : ((1?(5?7))?((6?2)?7)) M = 3, N = 2

if we put 3 plus (+) and 2 minus (-) then, ((1-(5-7))+((6+2)+7)) Answer : 18

How to tackle this Problem?

Thank you!

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
6 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

We can use Dynamic Programming to solve this problem dp state — [index][N][M] Where N=number of minus(-) left and M=number of plus(+) left

→ Reply