近日，B 站知名 Up 主「影视飓风」发布了一期视频，名字为《清晰度不如4年前！视频变糊是你的错觉吗？》，但因为背后牵扯的利益太重，最终视频不得已全网下架。
没有第一时间看过视频的你，相信一定和我一样好奇，视频到底讲了什么，背后牵扯到的蛋糕到底有多大。
互联网是有记忆的，发布过的东西就不可能毫无痕迹，即使发布者本身要全面下架，也不行。
我从海的那里找到了原视频，感兴趣的大家可以趁热观看：
为了防止视频被动丢失，这里再简单总结一下视频内容：
国内所有视频平台，为了节省存储和带宽，都对发布者的作品进行"压缩"，这很正常，其他视频网站也都这么干的。
但和其他视频网站不同的是，国内视频网站为了将成本压缩到极致，会采用一些不能确保用户体验的做法，最终为了"保能看"而"不保好看"，甚至于发布者上传两种清晰度的视频，高清的版本经过平台处理后，最终的播放效果还不如低清的版本。
这已经严重违背了用户「选择高清格式，是为看品质更高的视频」（甚至还是付费实现的），以及 Up 主「运用更昂贵的拍摄设备，是为了给用户呈现更好的内容」等初衷。
这还不是最离谱的。
某些平台，除了运用影响观感的压缩算法，平台甚至还会对原视频"动手"，例如增加视频的"锐度"，使其"看起来"更加清晰，但实则会丢失了大量细节。
而这一切，都仅仅为了能够极致地压缩成本。
要知道，国内视频平台普遍都实现了年几十亿的盈利，但还要做到这个程度，属实不应该。
...
考虑到大多数网友和我一样，对影视行业的专业知识了解不深，也不知晓"行业标准"到底如何。
这里再大概分享一些著名视频平台的码率，以 4K 视频为例：
YouTube：15 Mbps ~ 18 Mbps
Netflix：20 Mbps ~25 Mbps（保守估计）
Amazon：20 Mbps ~25 Mbps（保守估计）
HBO: 20 Mbps ~25 Mbps（保守估计）
某奇艺：2 Mbps ~ 5 Mbps（乐观估计）
某讯视频：2 Mbps ~ 5 Mbps（乐观估计）
某酷：2 Mbps ~ 5 Mbps（乐观估计）
简单来说，你可以将「码率」和「清晰度 + 流畅度」简单关联，如果一个视频码率过低，清晰度和流畅度都会大打折扣，通过和一些国际视频平台的码率对比，你应该知道视频说的"降低码率"有多离谱了。
...
回归主题。
来一道和 DP 相关的算法题。
题目描述
平台：LeetCode
题号：115
给定一个字符串 s 和一个字符串 t ，计算在 s 的子序列中 t 出现的个数。
字符串的一个 子序列 是指，通过删除一些（也可以不删除）字符且不干扰剩余字符相对位置所组成的新字符串。（例如，"ACE" 是 "ABCDE" 的一个子序列，而 "AEC" 不是）
题目数据保证答案符合 32 位带符号整数范围。
示例 1：
输入：s = "rabbbit", t = "rabbit"
输出：3
解释：
如下图所示, 有 3 种可以从 s 中得到 "rabbit" 的方案。
(上箭头符号 ^ 表示选取的字母)
rabbbit
^^^^ ^^
rabbbit
^^ ^^^^
rabbbit
^^^ ^^^
示例 2：
输入：s = "babgbag", t = "bag"
输出：5
解释：
如下图所示, 有 5 种可以从 s 中得到 "bag" 的方案。
(上箭头符号 ^ 表示选取的字母)
babgbag
^^ ^
babgbag
^^ ^
babgbag
^ ^^
babgbag
^ ^^
babgbag
^^^提示：
s 和 t 由英文字母组成
基本思路
有两个字符串 s 和 t，长度数量级都为
。
一个朴素的想法是，找出所有 s 的子序列，与 t 进行比较，找所有子序列的复杂度是
，肯定会超时。
因此，我们放弃这种朴素思路。
字符串匹配也不具有二段性质，不可能有
级别的算法，那么复杂度再往下优化就是
的递推 DP 做法了。
动态规划
DP 的状态定义猜测通常是一门经验学科。
但是，对于两个字符串匹配，一个非常通用的状态定义如下：
定义
为考虑 s 中
个字符，t 中
个字符的匹配个数。
那么显然对于某个
而言，从「最后一步」的匹配进行分析，包含两类决策：
不让 s[i] 参与匹配，也就是需要让 s 中
个字符去匹配 t 中的
字符。此时匹配值为
让 s[i] 参与匹配，这时候只需要让 s 中
个字符去匹配 t 中的
字符即可，同时满足 s[i]=t[j]。此时匹配值为
最终
就是两者之和。
Java 代码：
class Solution {
public int numDistinct(String s, String t) {
// 技巧：往原字符头部插入空格，这样得到 char 数组是从 1 开始
// 同时由于往头部插入相同的（不存在的）字符，不会对结果造成影响，而且可以使得 f[i][0] = 1，可以将 1 这个结果滚动下去
int n = s.length(), m = t.length();
s = " " + s;
t = " " + t;
char[] cs = s.toCharArray(), ct = t.toCharArray();
// f(i,j) 代表考虑「s 中的下标为 0~i 字符」和「t 中下标为 0~j 字符」是否匹配
int[][] f = new int[n + 1][m + 1];
// 原字符只有小写字符，当往两个字符插入空格之后，f[i][0] = 1 是一个显而易见的初始化条件
for (int i = 0; i <= n; i++) f[i][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
// 包含两种决策：
// 不使用 cs[i] 进行匹配，则有 f[i][j] = f[i - 1][j]
f[i][j] = f[i - 1][j];
// 使用 cs[i] 进行匹配，则要求 cs[i] == ct[j]，然后有 f[i][j] += f[i - 1][j - 1]
if (cs[i] == ct[j]) f[i][j] += f[i - 1][j - 1];
}
}
return f[n][m];
}}
C++ 代码：
class Solution {
public:
int numDistinct(string s, string t) {
int n = s.length(), m = t.length();
s = " " + s;
t = " " + t;
vector<vector<unsigned long long>> f(n + 1, vector<unsigned long long>(m + 1, 0));
for (int i = 0; i <= n; i++) f[i][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
f[i][j] = f[i - 1][j];
if (s[i] == t[j]) f[i][j] += f[i - 1][j - 1];
}
}
return f[n][m];
}};
Python 代码：
class Solution:
def numDistinct(self, s: str, t: str) -> int:
n, m = len(s), len(t)
s = " " + s
t = " " + t
f = [[0]*(m + 1) for _ in range(n + 1)]
for i in range(n + 1):
f[i][0] = 1
for i in range(1, n + 1):
for j in range(1, m + 1):
f[i][j] = f[i - 1][j]
if s[i] == t[j]:
f[i][j] += f[i - 1][j - 1]
return f[n][m]TypeScript 代码：
function numDistinct(s: string, t: string): number {
const n: number = s.length, m: number = t.length;
const f: number[][] = new Array(n + 1).fill(0).map(() => new Array(m + 1).fill(0));
for (let i: number = 0; i <= n; i++) f[i][0] = 1;
for (let i: number = 1; i <= n; i++) {
for (let j: number = 1; j <= m; j++) {
f[i][j] = f[i - 1][j];
if (s.charAt(i - 1) === t.charAt(j - 1)) f[i][j] += f[i - 1][j - 1];
}
}
return f[n][m];};
时间复杂度：
空间复杂度：
总结
关于字符串匹配，通常有两种（你也可以理解为一种）通用的状态定义：
表示「第一个字符 s 中
个字符」与「第二个字符 t 中
个字符」的匹配结果
表示「第一个字符 s 中
个字符」与「第二个字符 t 中
个字符」且 「最后一个字符为 t[j]」的匹配结果
往两个字符串的头部追加「不存在」的字符，目的是为了能够构造出可以滚动（被累加）下去的初始化值
进阶
事实上，关于字符串匹配问题，还有一道稍稍不同的变形的题目。
也是利用了类似的「通用思路」(状态定义) &「技巧」，然后对匹配过程中的字符进行分情况讨论，学有余力的同学可以看看：如何利用的「等差」性质降低「正则字符串匹配」算法复杂度
