avatar

光和尘

有花满渚、有酒盈瓯

目录检索关于我

🔖 最长公共子序列LCS

前言

一些定义:

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

最长公共子序列的长度

动态规划

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

🔖 最长上升子序列LIS

前言

最长上升子序列(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

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)sx真实最短距离D_x, (x \in V)

  • d_x 表示 sx当前已知最短距离,故 D_x \leqslant d_x 恒成立;

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

🔖 math函数极限

定义

  • 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

🔖 javascriptecmascript

?. 操作符

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

  • Demo

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

    等价于

     
    (o !== undefined && o !== null) ? o.prop : undefined
    (o !== undefined && o !== null) ? o['prop'] : undefined
    (f !== undefined && f !== null) ? f(arg1, arg2) : undefined
© 2017-2022 光和尘有花满渚、有酒盈瓯