wish_me's blog

A interesting DP problem
By wish_me, history, 7 years ago, In English

You are given a string and 2 operators ( & , | ). Return the total number of ways in which you can evaluate to true using the given string and operator set.

Example : Input : TF Output : 1 Input : TFF Output : 2 ( T | F & F , T | F | F )

  • Vote: I like it
  • -25
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I have come across a problem like this before. But i dont know how to solve it using dp. Someone explain please

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I will discuss it using recursion + memoization which can be easily converted to an iterative DP solution.

Let your state be where you are in the given string i, and what is the cumulative (Prefix) answer till now last.

Each time you can either AND this bit s[i] or OR it with last.

After finishing all the string, if last is true return 1, else return 0.

So the code may be something like: Assuming that s is the given string, mem is the memoization array filled initially by -1.

long long findMax(int i = 1, bool last = (s[0]=='T')){
   if(i==s.length())
       return last;
   long long & ret = mem[i][last];
   if(ret != -1)    return ret;
   return ret = findMax(i+1, last&(s[i]=='T')) + findMax(i+1, last|(s[i]=='T'));
}
→ Reply