算法题中常用数学概念、公式、方法汇总（其一：数列）

1. 本系列主要汇总了算法题中（尤其是一些模拟题）可能会遇到的数学概念、公式或方法，会持续进行补充和更新。
2. 这些数学的内容较为简单，不会超出高中数学的范畴。
3. 本文档中出现的代码均为Python代码，其他语言的实现也是类似的。

数列

等差数列

已知等差数列的首项（第$0$项）为$a_0$，公差为$d$。第$n$项的表达式为

$$a_n=a_0+nd$$

从第$0$项到第$n$项一共包含$n+1$项。前$n+1$项和的表达式为

$$S_{n+1}=(a_0+a_n)?(n+1)/2$$

即(首项+末项)*项数/2。代码表示为

an = a0 + n*d
S = (a0 + an) * (n+1) // 2

等比数列

已知等比数列的首项（第0项）为$a_0$，公差为$q$（$q\ne 0$）。第$n$项的表达式为

$$a_n=a_0?q^n$$

代码表示为

an = a0 * q**n

若$q=1$，则存在$a_n=a_0$，故前$$n+1$$项和的表达式为

$$S_{n+1}=a_0?(n+1)$$

代码表示为

S = a0 * (n+1)

若$q\ne 1$，则前$n+1$项和的表达式（本公式的证明可用错位相减法完成）为

$$S_{n+1}=a_0?\frac{1?q^{n+1}}{1?q}$$

代码表示为

S = a0 * (1 - q**(n+1)) / (1-q)

*数列的递推公式

描述一个数列通常有两种方式，通项公式和递推公式，如前文所列举的等差数列、等比数列的公式均为通项公式，他们的递推公式分别为$$a_n=a_{n?1}+d$$和$$a_n=a_{n?1}?q$$

可以看到，通项公式描述的是第$n$项和第$0$项之间的关系，递推公式描述的是第$n$项和第$n?1$项（或更多项）之间的关系。

在很多算法题目中，递推公式的应用是更加广泛的，如动态规划中的状态转移方程，本质上就是一种递推。

如经典的LeetCode509. 斐波那契数和LeetCode70. 爬楼梯，本质上都是用到了以下的递推公式

$$a_n=a_{n?1}+a_{a?2}$$

尽管斐波那契数列也可以通过待定系数法解出通项公式，即

$$a_n=\frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}}{2}{)}^n?(\frac{1?\sqrt{5}}{2}{)}^n]$$

即使通过直接代入$n$的方式，只需要O(1)的时空复杂度就可以得到计算结果，但在算法题几乎没有人会这样去实现代码。另外，我们可以看到，即便是如此简单的一个斐波那契数列，写成通项公式后也如此复杂，就更别说更加复杂的数列或序列了，因此除了简单的等差、等比数列以外，当涉及到数列的计算时，只需要老老实实按照递推关系式实现计算即可。

---

华为OD算法/大厂面试高频题算法练习冲刺训练

• 华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名！目前已服务100+同学成功上岸！

• 课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化

• 每期人数维持在20人内，保证能够最大限度地满足到每一个同学的需求，达到和1v1同样的学习效果！

• 60+天陪伴式学习，40+直播课时，300+动画图解视频，300+LeetCode经典题，200+华为OD真题/大厂真题，还有简历修改、模拟面试、专属HR对接将为你解锁

• 可上全网独家的欧弟OJ系统练习华子OD、大厂真题

• 可查看链接 大厂真题汇总 & OD真题汇总(持续更新)

• 绿色聊天软件戳 od1336了解更多