11.1-杨辉三角性质解法

自身有价值了，才会像吸铁石，朋友甚至以前的陌生人都愿意转身过来与你为伴，不要怪罪世界现实，让自己强大才是给自己最好的安全感！

真正想要的东西，
不只是踮踮脚尖那么简单，
所有的收获，一定要全力以赴，奋不顾身!

算法里面最经典的题目：（必须掌握*****）质数、杨辉三角、矩阵

列表在Python中是最重要的数据结构，数组在Java中也是最重要的数据结构；

面试题其实就是问你在这些基础解法上有优化策略没有（进行改进，变换）
算法中玩的就是这些东西；所以我们必须学到极致；

练习1.求杨辉三角的第m行的第n个元素：

杨慧三角性质：
1.第m行有m项，m为正整数，因此K一定不会大于m;
2.第N行的m个数可以表示为C(n-1,m-1),即从n-1个不同的元素中取m-1个元素的组合数；

#方法1：基本解法
最朴素的想法:下一行依赖于上一行所有元素，是上一行所有元素相加的和，再在两头各加1；
m = 6
n = 4

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


#方法2：一次开辟内存空间比 append方法速度要快
在不引起垃圾回收的情况下，方法2比1要好；效率与工资挂钩；

m = 6
n = 4

oldline = []
for i in range(m):
    newline = [1] * (i+1)
    
    for j in range(i-1):
        newline[j+1] = oldline[j] + oldline[j+1]
   
    # for j
    oldline = newline
    print(newline)
----------------------------------------------------
[1]
[1, 1]
[1, 2, 1]
[1, 3, 3, 1]
[1, 4, 6, 4, 1]
[1, 5, 10, 10, 5, 1]

组合数公式 ( 最快的方法)

从n个不同元素中取出m(m≤n)个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数。
公 式 C(n,m)=n!/((n-m)!*m!)（m≤n）
性质1 C(n,m)= C(n,n-m)
性质2 C(n,m)=C(n-1,m-1)+C(n-1,m)

# 方法3：性质2：阶乘思想n!/(r! * d!)
m = 6
k = 4

n = m-1
r = k-1
d = m-k

fact = 1
targets = []  # r,d, n n!/(r! * d!)
for i in range(1,n+1):
    fact *= i
    if r == i:     # 控制语句与单分支控制意义不同；’
        targets.append(fact)
    if d == i:
        targets.append(fact)
    if n == i:
        targets.append(fact)
print(targets[2] // (targets[0] * targets[1]))
----------------------------------------------------------------------------------
10

本节总结：

1. 计算机中，加法、乘法算的非常快的，效率极高；
2. %%timeit 测试的时候所有的print语句都要去掉；
3. 多行控制语句与单分支控制意义是不同的，存在多个条件时，单行会少考虑条件相等时进入分支的次数；