蓝桥杯Python组杨辉三角形

题目描述

杨辉三角形，是我国古代数学家杨辉在《详解九章算术》一书中所记载的。在这个三角形中，第一行只有一个数 1，以下每行的每个数，都是它左上方和右上方的两个数相加而成的。请输出第 n 行的数字。

输入格式:
输入只有一个正整数 n（1≤n≤30），表示要输出杨辉三角形的第 n 行。

输出格式:
输出一个列表，其中第 i 个元素表示第 n 行的第 i 个数的值。

样例输入：
4

样例输出：
[1, 3, 3, 1]

算法1

(暴力枚举) $O(n^2)$

直接根据杨辉三角的定义计算即可。

时间复杂度

暴力枚举，时间复杂度 $O(n^2)$。

Python 代码

n = int(input())
res = [1]
for i in range(1, n):
tmp = [1]
for j in range(1, i):
tmp.append(res[j-1] + res[j])
tmp.append(1)
res = tmp
print(res)

算法2

(线性递推) $O(n)$

根据杨辉三角的性质，第 n 行的第 i 个数可以表示为第 n - 1 行的第 i - 1 个数和第 i 个数的和，因此可以使用线性递推的方式计算。

时间复杂度

时间复杂度 $O(n)$。

Python 代码

n = int(input())
res = [1] * n
for i in range(1, n):
for j in range(i-1, 0, -1):
res[j] += res[j-1]
print(res)