DP Python solution


  • 1
    C

    dp is a good way to solve this problem. Every time when you increase the n by 1, you add 1 more digit in the front, which means you add 2**(n-1) to dp[n-1][-1] for you second half number list

    n = 1: [0,1]
    n = 2: [0,1]+ [2+0, 2+1][::-1] = [0,1,3,2]
    n = 3: [0,1,3,2] + [4 + 0, 4 +1, 4 +3, 4 + 2][::-1] = [0,1,3,2,6,7,5,4]

        def grayCode(self, n):
            dp = [[0]]
            for i in range(1,n+1):
                dp.append(dp[i-1] + [2**(i-1) + j for j in dp[i-1]][::-1])
            return dp[n]
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.