前言

一些定义：

• 公共子序列：对于给定数列 A=\lbrace a_1,a_2,\cdots,a_M \rbrace 和 B=\lbrace b_1,b_2,\cdots,b_N \rbrace，若 C=\lbrace c_1,c_2,\cdots,c_K \rbrace 既是 A 的子序列，又是 B 的子序列，则称 C 是 A 和 B 的公共子序列。
• 最长公共子序列：公共子序列中元素个数最多的那个。

最长公共子序列的长度

动态规划

记 dp(i,j) 表示 \lbrace a_1, a_2, \cdots, a_i \rbrace 和 \lbrace b_1, b_2, \cdots, b_j \rbrace 的最长公共子序列的长度，不难得到转移方程：

前言

最长上升子序列（LIS）是讲解动态规划算法的经典例题，使用朴素的动态规划算法可以在 O(N^2) 复杂度内求解；使用单调栈优化可以进一步将复杂度优化到 O(N \log N)。此外，不存在重复字符的最长公共子序列问题（LCS）可以转化成最长上升子序列问题进行求解，这使得部分 LCS 也可以在 O(N \log N) 复杂度内求解，相关内容在 最长公共子序列（LCS） 中进行了讨论，此处不再赘述。

一些定义：

• 上升子序列：对于数列 A=\lbrace a_1,a_2,\cdots,a_N \rbrace，若其某一子序列 B=\lbrace a_{b_1}, a_{b_2}, \cdots, a_{b_M}\rbrace 满足 b_i < b_{i+1}

Dijkstra 算法适用于 所有边权为正 的图；它同时适用于有向图和无向图。

约定

单元最短路径算法用于计算源点到图中所有点的最短距离。为方便表述，以下说明中进行如下约定：

• 记图 G 的点集为 V，边集为 E=\Big\lbrace (x,y) \big\vert x \in V, y \in V \Big\rbrace

• 记边权为 w_{x,y}（若存在多条从 x 连向 y 的边，取权值最小的那条）

• 记源点为 s, \; (s \in V)，s 到 x 的 真实最短距离 为 D_x, (x \in V)

• 记 d_x 表示 s 到 x 的 当前已知最短距离，故 D_x \leqslant d_x 恒成立；

为方便描述，以下称在边 (x,y) \in E

定义

• 设 f(x) 在点 x_0 的某一去心邻域内有定义，如果存在常数 A,\;\forall\,\epsilon > 0,\;\exists\,\delta > 0，当 0 < \lvert x-x_0 \rvert < \delta 时，有 \lvert f(x)-A \rvert < \epsilon，那么常数 A 称为函数 f(x) 在 x\rightarrow x_0 时的极限，记作：

  \lim_{x\rightarrow x_0}f(x)=A \quad\text{或}\quad f(x)\rightarrow A \text{（当}\;x\rightarrow x_0 \text{）}

  • 如果存在常数 A,\;\forall\,\epsilon > 0,\;\exists\,\delta > 0

?. 操作符

?. 是链式调用操作符，当操作符左侧变量不存在时会返回 undefined，并中断链式调用。其英文名称为 Optional chaining for property accesses and method calls

• Demo

   copy

  o?.prop
  o?.['prop']
  f?.(arg1, arg2)

  等价于

   copy

  (o !== undefined && o !== null) ? o.prop : undefined
  (o !== undefined && o !== null) ? o['prop'] : undefined
  (f !== undefined && f !== null) ? f(arg1, arg2) : undefined