基础 DP

$f[n]$：数列的第 $n$ 项.

$$f[n]= \begin{cases} 1&n=1,2\\ f[n-1]+f[n-2]&n\geq 3 \end{cases}$$

int f[];
f[1] = f[2] = 1;
for (int i = 3; i <= n; i ++)
    f[i] = f[i - 1] + f[i - 2];

$f[n]$：将 $n$ 个盘子从一杆移至另一杆，所需的最少移动次数.

将 $n$ 个盘子从 $a$ 杆移到 $c$ 杆，需要以下 $3$ 步：

1. 将 $a$ 杆的 $n-1$ 个盘子移至 $b$ 杆（共 $f[n-1]$ 次）.
2. 将 $a$ 杆的最后一个盘子移至 $c$ 杆（共 $1$ 次）.
3. 将 $b$ 杆的 $n-1$ 个盘子移至 $c$ 杆（共 $f[n-1]$ 次）.

$$f[n]= \begin{cases} 1&n=1\\ 2\cdot f[n-1]+1&n\geq 2 \end{cases}$$

int f[]; f[1] = 1;
for(int i = 2; i <= n; i ++)
    f[i] = 2 * f[i - 1] + 1;

$f[n]$：$n$ 对应的方法总数.

• 若第一个骨牌竖放在左边，则剩余 $2×(n-1)$ 个空方格，铺法数为 $f[n-1]$.
• 若第一个骨牌横放在左上角，为了不留空，第二个骨牌必须横放在其正下方. 剩余 $2×(n-2)$ 个空方格，铺法数为 $f[n-2]$.

$$f[n]= \begin{cases} 1&n=1\\ 2&n=2\\ f[n-1]+f[n-2]&n\geq 3 \end{cases}$$

状态转移方程几乎和 斐波那契数列 一致.

$a[n]$：$n$ 条封闭曲线分割成的区域个数.

由上图可得：

$$a[1]=2\\ a[2]-a[1]=2\\ a[3]-a[2]=4\\ a[4]-a[3]=6$$

即

$$a[n]=\begin{cases} 2&n=1\\ a[n-1]+2(n-1)&n≥2 \end{cases}$$

正确性证明：

新增一条曲线时，每与一条已有曲线相交一次，就增加一个区域. 而新增的第 $n$ 条曲线与已有的 $n-1$ 条曲线各有 $2$ 个交点

$∴$ 新增区域数 $=$ 新增交点数 $=2\cdot (n-1)$.

$∴$ 现有区域个数 $a[n]=$ 原有区域个数 $+$ 新增区域个数 $=a[n-1]+2(n-1)$.

int a[]; a[1] = 2;
for(int i = 2; i <= n; i ++)
    a[i] = a[i - 1] + 2 * (n - 1);

$f[i]$：$\text{LIS}(A_{1\cdots i})$ 的长度.

枚举 $j=1\cdots i-1$：

• 若 $A_j<A_i$，则 $A_i$ 可以接在 $\text{LIS}(A_{1\cdots j})$ 后面，形成的上升子序列长度为 $f[j]+1$.
• 若 $A_j≥A_i$，$A_j$ 对 $f[i]$ 没有贡献，直接跳过.

$$f[i]=\max_{j<i, \ A_j<A_i}(f[j]+1)$$

for (int i = 1; i <= n; i ++) {
    f[i] = 1;
    for (int j = 1; j < i; j ++)
        if (a[j] < a[i])
            f[i] = max(f[i], f[j] + 1);
}
// 问题的解是 f[n]

扫描每一个数，将其加入单调栈.

假设当前单调栈内有 $\{2,3,6\}$，而扫描到 $4$. 根据贪心原理，将 $6$ 替换为 $4$ 必定更优.

当扫描到 $a[i]$：

• 若 $a[i]$ 大于栈尾，则直接将其入栈.
• 否则在栈中二分查找第一个 $\geq a[i]$ 的数，将其替换为 $a[i]$.

最终栈的长度即为 LIS 的长度. 时间复杂度为 $O(n\log{n})$.

vector<int> s;
s.push_back(a[1]);
for (int i = 2; i <= n; i ++) {
    if(a[i] > s.back())
        s.push_back(a[i]);
    else
        *lower_bound(s.begin(), s.end(), a[i]) = a[i];
}

$f[i,j]$：$\text{LCS}(A_{1\cdots i},B_{1\cdots j})$ 的长度.

枚举 $i=1\cdots n$： 枚举 $j=1\cdots m$：

• 若 $A_i\not=B_j$，继承最优子状态：$f[i,j]=\max(f[i-1,j],f[i,j-1])$.
• 若 $A_i=B_j$，则 $A_i$（或 $B_j$）可以接在 $\text{LCS}(A_{1\cdots i-1},B_{1\cdots j-1})$ 之后，形成的公共序列长度为 $f[i-1,j-1]+1$.

$$f[i,j]=\max\left\{\begin{aligned} &f[i-1,j]\\ &f[i,j-1]\\ &f[i-1,j-1]+1,A_i=B_j \end{aligned}\right.$$

for (int i = 1; i <= n; i ++) {
    for (int j = 1; j <= m; j ++) {
        f[i][j] = max(f[i - 1][j], f[i][j - 1]);
        if (a[i] == b[j])
            f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
    }
}

$(i,j)$：第 $i$ 行第 $j$ 列的数字.

$f[i,j]$：走到 $(i,j)$ 时，经过的数字之和的最大值.

逆推法：要走到 $(i,j)$，则上一步只能在 $(i-1,j-1)$ 或 $(i-1,j)$.

$$f[i,j]=(i,j)+\max\left\{\begin{aligned} &f[i-1,j-1]\\ &f[i-1,j] \end{aligned}\right.$$

注意：当 $j=1$ 或 $j=i$ 时，$f[i-1,j-1]$ 和 $f[i-1,j]$ 会越界. 故 $f$ 数组须初始化为 $-∞$，以使越界的元素在 $\max$ 操作中被自动淘汰.

memset(f, 0x80, sizeof f);
f[1][1] = 1;
for (int i = 2; i <= n; i ++) {
    for (int j = 1; j <= i; j ++) {
        cin >> f[i][j];
        f[i][j] += max(f[i - 1][j - 1], f[i - 1][j]);
    }
}
for (int i = 1; i <= n; i ++)
    ans = max(ans, f[n][i]);

$(i,j)$：第 $i$ 行第 $j$ 列的数字.

$f[i,j]$：走到 $(i,j)$ 时，经过的数字之和的最大值.

逆推法：由于只能向左走或向下走，要走到 $(i,j)$，上一步只能在 $(i-1,j)$ 或 $(i,j-1)$.

$$f[i,j]=(i,j)+\max\left\{\begin{aligned} &f[i-1,j]\\ &f[i,j-1] \end{aligned}\right.$$

注意：当 $i=1$ 或 $j=1$ 时，$f[i-1,j]$ 和 $f[i,j-1]$ 会越界. $f$ 数组须初始化为 $-∞$.

memset(f, 0x80, sizeof f);
for (int i = 1; i <= n; i ++) {
    for (int j = 1; j <= m; j ++) {
        cin >> f[i][j];
        if (!(i == 1 && j == 1))
            f[i][j] += max(f[i-1][j], f[i][j - 1]);
    }
}