2020-05-07 盗梦空间之递归笔记

I found myself not as enthusiastic as before.

---

Recursion
关于递归，用超哥的话来讲：类比于盗梦空间，每一个空间都可以看做是一种其他空间的复制，其中与参数(主角)无关的量都是不变的，唯一改变的是由参数引起的变化。在算法题中，最直观的是求n!的问题。将原始问题分解为很多个重复的子问题，按照层层向下(解决更小的子问题)递归的思路，做出当前层的process，并向下进行递归，最终得到问题的结果。

超哥的洋葱图.jpg

可以看到n!的问题像是一个斜放的金字塔，上半部分是对于问题的拆解，将原始问题转化为n个重复的子问题，下半部分是对子问题的求解，从而得到原始问题的解。在实际的问题中，系统也是为我们准备了这样一个栈结构来解决递归问题。

递归问题的解决python代码模板：

def recursion(level, param1, param2, ...):
    # step1:递归终止条件
    if level > MAX_LEVEL:
        process_result
        return
    # step2:处理当前层逻辑
    process(level, data, ...)
    # step3:下探到下一层
    recursion(level+1, param1, param2, ...)
    # step4:清理当前层（全局变量等）

Query:生成n对小括号（）问题

step-1：假设不考虑括号的合法性，此时可以将其看做排列组合问题，总计为2n个位置，放置左括号“（ ”和右括号“）”。此放置问题，对于每个位置也是一个递归的问题。

res = []
def generate(level, MAX_LEVEL, cur_s):
    # 终止条件
    if level >= MAX_LEVEL:
        res.append(cur_s)
        return
    # 当前层逻辑
    s1 = cur_s + ')'
    s2 = cur_s + '('
    # 重复子问题
    generate(level+1, MAX_LEVEL, s1)
    generate(level+1, MAX_LEVEL, s2)
    # 清理当前层
    pass

if __name__ == '__main__':
    n = 3
    generate(0,2*n,'')
    print(len(res))
    print(res)

结果输出：

64
['))))))', ')))))(', '))))()', '))))((', ')))())', 
')))()(', ')))(()', ')))(((', '))()))', '))())(', 
'))()()', '))()((', '))(())', '))(()(', '))((()', 
'))((((', ')())))', ')()))(', ')())()', ')())((',
 ')()())', ')()()(', ')()(()', ')()(((', ')(()))',
 ')(())(', ')(()()', ')(()((', ')((())', ')((()(', 
')(((()', ')(((((', '()))))', '())))(', '()))()',
 '()))((', '())())', '())()(', '())(()', '())(((', 
'()()))', '()())(', '()()()', '()()((', '()(())',
 '()(()(', '()((()', '()((((', '(())))', '(()))(', 
'(())()', '(())((', '(()())', '(()()(', '(()(()',
 '(()(((', '((()))', '((())(', '((()()', '((()((', 
'(((())', '(((()(', '((((()', '((((((']

可以看到对于不考虑括号合法性的中间解过程，是所有的可能结果的全排列，总数为2^6=64。

step-2：考虑如何从中间解中挑选出满足合法性的括号。通过对合法性括号对的分析，可以得出左右括号数量都需要等于n，并且右括号需要匹配左括号。也就是在放置括号时，不能像全排列那样随意的放置左右括号，因此需要满足以下条件：a.左括号随时可以放，但是总数不能超过n；b.右括号放置时需要对前面左括号的数量进行匹配，满足小于左括号才能放置。

res = []
def generate_(left, right, MAX_LEVEL, cur_s):
    # 终止条件
    if left == MAX_LEVEL and right == MAX_LEVEL:
        res.append(cur_s)
        return
    if left < MAX_LEVEL:
        # 当前层逻辑
        s1 = cur_s + '('
        # 重复子问题
        generate_(left+1, right, MAX_LEVEL, s1)
    if right < left:
        # 当前层逻辑
        s2 = cur_s + ')'
        # 重复子问题
        generate_(left, right+1, MAX_LEVEL, s2)
    
    # 清理当前层
    pass
 
if __name__ == '__main__':
    n = 3
    generate_(0, 0, n, '')
    print(len(res))
    print(res)

结果输出：

5
['((()))', '(()())', '(())()', '()(())', '()()()']

---

• 递归问题思维要点：
  1.找到最近最简方法，将其拆解为可重复解决的问题（重复子问题）
  2.数学归纳法

Divide_conquer

Query: 求取pow(x, n)

#2020-05-08 分治
def pow_(x, n):
    # 终止条件
    if n == 0:
        return 1.0
    if n == 1:
        return x
    # 对问题进行分解
    half = n/2
    # 下探到下一层
    res = pow_(x, half)
    # 结果组合
    if n % 2 == 1:
        res = res * res * x
    else:
        res = res * res
    # revert
    pass

    return res

def pow_call(x,n):
    n_ = abs(n)
    res = pow_(x,n_)
    if n < 0:
        res = 1.0/res

    print(res)

if __name__ == '__main__':
    #solve pow(x, n)
    print("pow(3,-2)="),
    pow_call(3,-2)
    print("pow(3,2)="),
    pow_call(3,2)
 

结果输出：

pow(3,-2)= 0.111111111111
pow(3,2)= 9

Query: subset problem

def subset_(nums):
    #初始化为空集
    res = [[]]
    for num in nums:
        #对于t来说本身就是一个集合形式
        res += [t + [num] for t in res]
    return res

if __name__ == '__main__':
    print(subset_([1,2,4]))

结果输出：

all subsets: [[], [1], [2], [1, 2], [4], [1, 4], [2, 4], [1, 2, 4]]

DONE