# 基础

# 优化

# 滚动数组

由于 dp 二维表最终只要最后一行最后一列的数据，因此可以用滚动数组，只保留一行数据进行遍历。好像要从大到小。

# 字符串

# 最长公共子序列

• str1 的长度为 m，str2 的长度为 2
• dp[i][j] 表示长度为 i 的 str1 子串和长度为 j 的 str2 子串的最长公共子序列的长度。子串取 [0:i) 或 [0:j) 范围的字符串。
• i 和 j 均从 0 开始增长。

if (str1[i]==str[j])
	dp[i][j] = dp[i-1][j-1] + 1;
else
	dp[i][j] = max(dp[i][j-1], dp[i-1][j]);

子串和子序列不同！

$$\sum^\infin_{n=1} \frac{(z-1)^n}{5^n}$$

# 背包

0-1 背包

dp 遍历。

dp[i][j] i 物品编号， j 背包大小。表示当背包