1. class Solution:
    2.     def kthGrammar(self, N: int, K: int) -> int:
    3.         old_string = '0'
    4.         for i in range(1, N):
    5.             new_string = ''
    6.             for ch in old_string:
    7.                 if ch == '0':
    8.                     new_string += '01'
    9.                 else:
    10.                     new_string += '10'
    11.             old_string = new_string
    12.         return old_string[K - 1]

    超时！

    找出递推关系。通过题目可以知道，第N行的元素是由第N-1行的元素确定的，且第N-1行的一个元素依次确定第N行的两个元素。所以我们可以得出，第N行的第K个元素由第N-1行的第（K+1）/2个元素确定。并且我们可以分类K的奇偶和（K+1）/2的取值得出递推关系
    3. 找出边界条件。当N=1时，直接返回0.

    作者：serendipity-3s
    链接：https://leetcode-cn.com/problems/k-th-symbol-in-grammar/solution/779di-kge-yu-fa-fu-hao-by-serendipity-3s/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

    一般而言，第 K 位的父位应该是第 (K+1) / 2 位。如果父位是 0，那么这一位就是 1 - (K%2)。如果父位是 1，那么这一位就是 K%2。

    1. class Solution(object):
    2.     def kthGrammar(self, N, K):
    3.         if N == 1: return 0
    4.         return (1 - K%2) ^ self.kthGrammar(N-1, (K+1)//2)