 # How to Translate recursion into DP?

This question was asked in CodeChef Starters 10 Division 2 (Rated), I solved this question using recursion ( which failed because it got TLE).
I tried my best to convert it into DP but wasn’t able to do it.

Question Name: Magical Flips (CRDFLP)

My Code:

``````def solve(idx, prev_and, flips):
global max_and
global min_flips
if idx == n:
if prev_and > max_and:
max_and = prev_and
min_flips = flips
return

solve(idx+1, prev_and&arr[idx], flips)
solve(idx+1, prev_and&brr[idx], flips+1)

for _ in range(int(input())):
n = int(input())
arr = list(map(int, input().split()))
brr = list(map(int, input().split()))
max_and = -1
min_flips = 0
d = dict()
solve(0, 2**31-1, 0)
print(max_and, min_flips)
``````

My Logic: My logic was simple, for each card we have 2 options either we take the front face card number in our final result or we take the back face number, and then we have to calculate the maximum and from all available combinations.
My code is currently O(2^n) but by using DP it can be reduced.

Only suggestions will also be helpful ( or code in any language )

This logic is incorrect! Try to think why it’s wrong 