算法可视化
入门执行逻辑
最长公共子序列 LCS
dp[i][j] = 两个字符串前 i、j 个字符的最长公共子序列。字符相等取左上+1,不等取上/左较大者。
main.cpp第 2 行
1// LCS: dp[i][j] = a 前 i 个和 b 前 j 个的最长公共子序列
2for (int i = 1; i <= n; i++)
3 for (int j = 1; j <= m; j++)
4 if (a[i-1] == b[j-1])
5 dp[i][j] = dp[i-1][j-1] + 1;
6 else
7 dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
8// 答案: dp[4][4] = 3
变量表0 个变量
还没有变量,执行到声明语句后出现
DP 表格(行=前 i 个物品, 列=容量)
| A | C | B | D | ||
|---|---|---|---|---|---|
| A | 0 | 0 | 0 | 0 | 0 |
| B | 0 | ||||
| C | 0 | ||||
| D | 0 | ||||
| 4 | 0 |
本格取物品本格不取最优路径
1/18
dp 表初始化:第 0 行和第 0 列都是 0(空串公共子序列长度为 0)
1 / 18