动态规划经典算法课堂笔记

---

1. 最长上升子序列（LIS）- O(n log n)优化

核心思想

维护一个 dp 数组，dp[i] 表示长度为 i 的 LIS 的最小末尾元素，通过贪心+二分查找优化时间复杂度。

状态定义

• dp[cnt]：长度为 cnt 的 LIS 的最小末尾值。

算法流程

1. 遍历数组，若当前元素 a[i] > dp[cnt]，则直接延长 LIS（dp[++cnt] = a[i]）。
2. 否则，二分查找第一个 >= a[i] 的位置 sb，替换 dp[sb] = a[i]（为后续元素留出更大空间）。

关键代码

int ef(int x){ // 二分查找第一个 >= x 的位置
    int l=1,r=cnt,ans=-1;
    while(l<=r){
        int mid=l+r>>1;
        if(dp[mid]>=x)ans=mid,r=mid-1;
        else l=mid+1;
    }
    return ans;
}

---

2. 编辑距离（Levenshtein Distance）

核心思想

通过动态规划计算将字符串 s1 转换为 s2 所需的最少操作数（插入、删除、替换）。

状态定义

• dp[i][j]：s1 前 i 个字符与 s2 前 j 个字符的编辑距离。

转移方程

• 若 s1[i] == s2[j]：dp[i][j] = dp[i-1][j-1]（无需操作）。
• 否则：dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1（取插入、删除、替换的最小操作数+1）。

初始化

• dp[i][0] = i（s1 前 i 个字符全删除）。
• dp[0][j] = j（s2 前 j 个字符全插入）。

---

3. 最大平均值和的分组

核心思想

将数组前 i 个元素分成 j 组，通过枚举最后一组的起始位置 k，求最大平均值和。

状态定义

• dp[i][j]：前 i 个元素分成 j 组的最大平均值和。

转移方程

• dp[i][j] = max(dp[i][j], dp[k-1][j-1] + f(k, i))，其中 f(k, i) 是 a[k..i] 的平均值。

初始化

• 当 j == 1 时，dp[i][1] = f(1, i)（前 i 个元素作为一组）。

---

4. 无重复字符子串的最大价值

核心思想

dp[i] 表示前 i 个字符的最大价值，通过向前枚举无重复字符的子串更新状态。

状态定义

• dp[i]：前 i 个字符的最大价值。

算法流程

1. 遍历每个位置 i，用 map 记录字符是否重复。
2. 从 i 向前枚举 j，若 s[j] 重复则停止；否则 dp[i] = max(dp[i], dp[j-1] + a[i-j+1])。

---

5. 最长公共子序列（LCS）

核心思想

通过动态规划求两个序列的最长公共子序列长度（子序列不要求连续）。

状态定义

• dp[i][j]：序列 a 前 i 个元素与序列 b 前 j 个元素的 LCS 长度。

转移方程

• 若 a[i] == b[j]：dp[i][j] = dp[i-1][j-1] + 1（公共子序列延长）。
• 否则：dp[i][j] = max(dp[i-1][j], dp[i][j-1])（取去掉 a[i] 或 b[j] 的最大值）。