9.3-杨辉三角对称解法和单行列表解法

人世间的东西，一半是不值得争的，一半是不需要争的。我们真正所要追求的，并不在于比别人拥有更多的财富、或者比别人优秀，而在于不断超越从前的自我。

本章节的关键问题：

list不应该使用的方法：
中间删除、中间插入，列表相加（大数据）出新list（空间复杂度增加），容器列表空间的循坏开辟；

杨辉三角多种解法：对称解法和单行列表解法

1.分奇数行与偶数行；
2.每行第二个数为自然数
3.第N行有N项；

从小到大解决问题

方法3：先构建列表空间，在填充数值；
n=6
tri = [[1],[1,1]]   # 0,1

for i in range(2,n):  #[0,5]
#     row = [1]
#     for j in range(i):
#         row.append(1 if j == i-1 else 0)       #思考数字填充覆盖的过程；
    row = [1]*(i+1)   #效率高

    pre = tri[i-1]
    
    for j in range(i-1):
        row[j+1] = pre[j] + pre[j+1]
    tri.append(row)
print(tri)
----------------------------------------------------------
[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1], [1, 5, 10, 10, 5, 1]]

方法4：对称性解法：
tri = [[1],[1,1]]   # 0,1

for i in range(2,n):  #[0,5]
    row = [1]*(i+1)
    pre = tri[i-1]
    
    for j in range(i//2):
        val = pre[j] + pre[j+1]
        row[j+1] = val #1
        if i != 2j:
            row[-j-2] = val
    tri.append(row)
print(tri)
----------------------------------------------------
[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1], [1, 5, 10, 10, 5, 1]]



方法4变体1：对称性解法：空间复杂度进一步降低；
n = 6
row = [1]*n   #一次性开辟足够的空间；

for i in range(n):
    offset = n-i
    z=1 #因为会有覆盖影响计算，索引引入一个临时变量；
    for j in range(1,i//2+1):
        val = z + row[j]
        row[j],z = val,row[j]
        if i != 2*j:
            row[-j-offset] = val
    print(row[:i+1])
----------------------------------------------
[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]
[1, 5, 10, 10, 5, 1]