杨辉三角蕴含的编程哲学

这是一道非常妙的面试题，并没有涉及到动态规划等比较复杂的算法，但是通过手写代码却可以区分出面试者的水平，尤其是在工作中编程的素养。应届生往往会认为这是一道送分题，不假思索的给出答案，结果却漏洞百出；水平一般的程序员则会考虑到一些边界情况的处理，从而保证功能的正确性；而久经沙场的程序员，不仅知道哪里需要优化，还会考虑到程序在线上环境运行的健壮性。

源码地址

CONTENTS

问题
解（python实现）
总结

问题

我们从小学就接触过的杨辉三角，在国外被称为帕斯卡三角形（Pascal's triangle），前9行写出来如下：

　　　　　　　　１
　　　　　　　１　１
　　　　　　１　２　１
　　　　　１　３　３　１
　　　　１　４　６　４　１
　　　１　５　10　10　５　１
　　１　６　15　20　15　６　１
　１　７　21　35　35　21　７　１
１　８　28　56　70　56　28　８　１

可以这样定义杨辉三角：

第n行的数字个数为n个
除每行最左边与最右边的数字为1以外，每个数字等于它的左上方与右上方两个数字之和（也就是说，第n行第k个数字等于第n-1行的第k-1个数字与第k个数字的和）

问题是这样的：实现一个接口给线上用，求第n行第k个数字。函数的签名如下：

def solve(n, k):
    pass

解（python实现）

递归实现

根据定义很容易使用递归来实现，并且递归版本的代码一如既往的简洁：

pt_recursive.py:50分

def solve(n, k):
    if k==1 or k==n:
        return 1
    return solve(n-1, k-1) + solve(n-1, k)

然而，求第n行第k个数字时，它上面的某些数字会被重复计算很多遍，性能极低。另一方面，递归代码的调用栈过长，函数调用开销大，并且很容易超出最大递归层数的限制。

迭代实现

pt_iteration1.py:50分

把上面的代码用迭代改写：

def solve(n, k):
    L = [[]]
    for i in range(1, n+1):
        l = [None]
        for j in range(1, i+1):
            if j==1 or j==i:
                v = 1
            else:
                v = L[i-1][j-1] + L[i-1][j]
            if i==n and j==k:
                return v
            l.append(v)
        L.append(l)

该答案从第一个数字开始遍历到目标为止，没有重复计算，但是内存占用很高，所以需要优化空间，完全没有必要保留前面遍历过的所有数字。

pt_iteration2.py:60分

遍历的时候只需要保留上一行的数字，代码如下：

def solve(n, k):
    for i in range(1, n+1):
        l = [None]
        for j in range(1, i+1):
            if j==1 or j==i:
                v = 1
            else:
                v = ll[j-1] + ll[j]
            l.append(v)
        ll = l # keep last line
    return ll[k]

内存问题解决了，但还是不够高效，时间复杂度是N平方。

pt_iteration3.py:65分

借助python的列表生成器，上面的解法可以写的非常优雅，然而对于性能却毫无帮助：

# add 0 in 2 sides
def triangles1():
    l = [1]
    while True:
        yield l
        l.append(0)
        l = [l[i-1] + l[i] for i in range(len(l))]

# zip
def triangles2():
    l = [1]
    while True:
        yield l
        l = [sum(t) for t in zip([0]+l, l+[0])]

def solve(n, k):
    for l in triangles1():
        n -= 1
        if n==0:
            return l[k-1]

如果需要输出/打印整个杨辉三角，那么最优解是pt_iteration3。

组合数

杨辉三角有很多规律，其中有一条对于解答本题很关键：

第n行的第k个数字恰好为组合数(n-1)C(k-1)

通过直接计算组合数就可以避免遍历所有的数字，时间复杂度将为N。

pt_combination1.py:70分

该问题转化为计算组合数：\[C_{n}^k = \frac{n!}{k!(n-k)!}\] 该公式可以从排列数推导出来。

import operator

def fac(n):
    if n == 0:
        return 1 # 0! = 1
    return reduce(operator.mul, range(1,n+1))

def c(n, k):
    return fac(n)/(fac(k)*fac(n-k))

def solve(n, k):
    return c(n-1, k-1)

代码足够精简了，但是计算阶乘的时候有大量重复的计算，还可以优化。

pt_combination2.py:80分

因为\[\frac{n!}{k!(n-k)!} = \frac{n(n-1)...(n-k+1)}{k(k-1)...1}\]

import operator

def c(n,k):
    if k == 0:
        return 1
    return reduce(operator.mul, range(n-k+1, n+1))/reduce(operator.mul, range(1, k+1))

def solve(n, k):
    return c(n-1, k-1)

当k == 0时，range返回空列表，reduce报错，所以必须特殊处理。

pt_combination3.py:90分

如果传入的参数是(1000, 1000)，那么上面的方法需要计算两遍999的阶乘，而计算阶乘是比较耗时的，考虑到这种特殊情况，当n == k时，直接返回1，代码如下：

import operator

def c(n,k):
    if k == 0:
        return 1
    if n == k:
        return 1
    return reduce(operator.mul, range(n-k+1, n+1))/reduce(operator.mul, range(1, k+1))

def solve(n, k):
    return c(n-1, k-1)

满分答案

到目前为止，我们的代码很优雅也很高效，但我们忘了题目的要求——要给“线上使用”。在线上环境我们不能保证传入的参数是合法的，比如k比n大，比如n超过了上限，导致溢出或者超出计算能力，因此需要对参数的类型、范围等进行校验。这里为了简单处理，对于不合法的参数返回None，线上的话最好有日志和错误信息，方便排错，提到这一点就是加分项。

pt_final.py:100分

import operator

def c(n,k):
    if k == 0:
        return 1
    if n == k:
        return 1
    return reduce(operator.mul, range(n-k+1, n+1))/reduce(operator.mul, range(1, k+1))

def check(n, k):
    for a in (n, k):
        if type(a) is not int:
            return False
        if not (a >= 1 and a <= 30000):
            return False
    if k > n:
        return False
    return True

def solve(n, k):
    if not check(n, k):
        return None
    return c(n-1, k-1)

虽然python中的int没有上限，但是当n足够大时（一般是异常情况），会导致服务被占用，因此有必要限制最大值。

总结

希望读者可以体会到以下几点编程的哲学：

在学校和公司编程的差别在于，学校只要求输出正确的结果，而公司还注重优化性能和在线上环境的健壮性；
如果说算法是程序的灵魂，那么数学就是计算机的灵魂，很多复杂的编程问题都可以借助于数学的手段化简为繁；
解决一个问题有很多方法，然而最优解只有一个；