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)
Question Link: https://www.codechef.com/START10B/problems/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 )

Thanks in advance.

Well, I don’t think here dp can even work. If you thought something like this, dp (i)(0) = max (dp (i-1)(0)&back(i),dp(i-1)(1)&back(i)); Here dp (i)(0) means the maximum number that can be obtained if you have cards from index [1…2…3…4…i] with card i facing it’s back side. Dp (i)(1) denotes the same except the card i is now facing front side.

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

The main issue is that when dp (i)(0) doesn’t come from max(dp (i-1)(0) or dp (i-1)(1) )(both are the maximum numbers obtained when cards upto index i-1 are considered.

Example,The cards are (their numbers {front,back} are in binary) {1001,0111} {1111,0110} {0111,0011}. Here dp (2)(1) is 1001 and dp (2)(0) is 0110, but dp(3)(1) is 0111 which comes 0111 & 1111 & 0111 , which neither involves dp(2)(1) or dp (2)(0). The thinking that maximum no. comes from some previous state having maximum number itself is wrong.

1 Like

Thanks for your response.
I thought of the same when I was trying to solve this, but since I am not that good in DP, I thought there may be a way (that I don’t know) to optimize this recursion where I don’t have to calculate all the possible 2^n combinations.