米哈游（原神）一面算法变形题
又见彩票事件
1月17日，中国体彩最新开奖结果出炉，其中“排列3”和“排列5”均出现罕见的“连5”组合。
体彩“排列3”的开奖号码为“555”，“排列5”的开奖号码为“55555”。
5亿奖池被清空。
开奖后第二天就有同学问我怎么看。
我 ... 我能怎么看？
2.2 亿 的时候我已经看过了，也把结论分享过给大家了。
果然，1月18号这事儿上热搜之后，我们又一次的迎来最具"说服力"的回应：
?1月18日，相关话题冲上微博热搜，有网友质疑开奖号码过于罕见和特殊，是否存在内幕。对此，中国体彩客服回应记者称，“开奖全流程有网络直播，也有两名工作人员的监督，号码是随机摇出来的，不存在内幕和故障，开奖是真实有效的。” ?
这里面的重点，也是在普通人常识里最有说服力，最能实现逻辑自洽的，是「监督」二字。
...
其实也难怪大家来问我看法。
虽然我已经在 1月10号 的推文中详细说过彩票问题，但文章似乎被平台精准限流了。
在我近期的发文中，那篇文章的阅读是倒数第一。
如果是和「前一天」及「后一天」的推文去比较，则更是突兀到不行。
我十分好奇这里面到底存在什么玄学因素。
于是，我萌生了把这些“似乎有风险“，会被公众号推荐系统标记的内容重发一遍。
直接对那天的推文中的「彩票」部分内容进行截图贴出，我估计是可以绕过某些机制，让阅读回归到正常水准的。
但，那又有什么意思呢？
我就是要看看，对于一些无法反驳的事实，简中网是如何让文章不被看到的。
以下看到的内容，是对 1月10号 推文中「锐评时事」部分的完全复制。
...
本来今天不打算更新闻的了，中午的时候看到「花10万中2.2亿彩票事件调查进展」上热搜。
原以为总算和"融创"来了点不一样的了。
结果调查结果是暂无结果，调查进展是没有进展。
一则报道，没有实际的信息增量，但有广泛的群众记忆和讨论基础。
使得报道发出之后，话题稳坐热搜榜的第二名。
只要能骂能喷，能对外输出情绪，群众从不在意这是新闻还是旧闻，有意义还是没意义。
如果你问我，如何理解彩票事件。
能问出这样的问题，那么大概率你对福利彩票的认识存在较大盲区。
嗯，是盲区，而不是误区。
我这里简单列举一些基本信息：
- 彩票中心的博彩专营权是由国务院给予的，主要目的是通过发售彩票，来增加财政收入
- 目前福利彩票的开奖过程，都是有公证人在场的
- 公证人来自于公证机构，公证机构的公证权是由国家直接下放，即不存在自由经济市场产生的公证企业，必须是国家司法证明机构，才能行使公证权
看到这里，一切正常，逻辑闭环。
也符合普罗大众对彩票事业的理解。
可能大家印象中的细节没有这么足，但结论肯定是大差不差：彩票的公平性由国家直接或间接保证。
但稍微深究就可以发现当中的不合理关系，我补充一些大家可能不知道的信息：
- 公证机构虽然是由国家直接下放公证权，但不属于公务员体系，是自收自支的事业单位
- 开奖过程的公证人在场，并非规定的条例，而是彩票中心为了自身形象，多卖彩票，花钱从公证机构请的。主要作用不得而知，但个人猜想，如果现场有公证人，那么开奖过程中，增加一个公证人宣誓的环节，会在观众心理上增加许多正面作用
现场公证员的拿着背靠国家的公证权，但位于自收自支的事业单位，可能会有对权力进行变现的局部压力，彩票中心作为现场公证人的甲方，可能也会影响公证人员的立场。
这里也有必要声明一下，上述只是基于现有规则进行的动机猜测，不代表事实本身。
任何有独立思考能力的人都会有自己的想法。
但彩票的本质终归不是数学。
搞清楚这些之后，你可能要推翻以前对福利彩票的认识了。
但普通人接受到这些信息之后，可能只够在一段时间内，认识到「彩票不是一个概率游戏」，长期还是会落入「用数量对抗随机性」的不切实际幻想中。
归根到底，是这些利害关系不足以产生画面感。
无法与报道刊登的「xxx 中 xxxx 万元」形成对立效果。
因此，我有必要提供一个具体的场景，断了大家通过彩票致富的念想。
你可以把这游戏看作是一场特殊「剪刀石头布」：赢了得 500w，输了赔 2 元，但永远是对方先出。如果对方一时间头脑发热出错了，他有权判定无效，重开一盘。
好，现在我已经将一个画面深深植入你的脑海。
大概率足够你对现有的体制下的游戏产生免疫效果。
...
好，复述完毕。
如果本推文达到了阅读的平均水准，那么很好，之前没被传播出去的东西，现在有了二次机会。
如果本推文没有达到阅读的平均水准，那么至少你和我都见证了某些无形的东西，亦具意义。
...
回归主线。
过去一周，大家对米哈游（原神）的一面算法题十分感兴趣，但那道题毕竟太裸（太模板）了。
所以这次，我给大家安排了一道「变形题」试试。
题目描述
平台：LeetCode
题号：1035
在两条独立的水平线上按给定的顺序写下 s1 和 s2 中的整数。
现在，可以绘制一些连接两个数字
和
的直线，这些直线需要同时满足满足：
- 且绘制的直线不与任何其他连线（非水平线）相交。
请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。
以这种方法绘制线条，并返回可以绘制的最大连线数。
示例 1：
输入：s1 = [1,4,2], s2 = [1,2,4]
输出：2
解释：可以画出两条不交叉的线，如上图所示。
但无法画出第三条不相交的直线，因为从 s1[1]=4 到 s2[2]=4 的直线将与从 s1[2]=2 到 s2[1]=2 的直线相交。
示例 2：
输入：s1 = [2,5,1,2,5], s2 = [10,5,2,1,5,2]
输出：3
示例 3：
输入：s1 = [1,3,7,1,7,5], s2 = [1,9,2,5,1]
输出：2
提示：
动态规划
这是一道「最长公共子序列（LCS）」的轻度变形题。
对于这类题都使用如下「状态定义」即可：
代表考虑
的前
个字符、考虑
的前
的字符，形成的最长公共子序列长度。
然后不失一般性的考虑
如何转移。
由于我们的「状态定义」只是说「考虑前
个和考虑前
个字符」，并没有说「一定要包含第
个或者第
个字符」（这也是「最长公共子序列 LCS」与「最长上升子序列 LIS」状态定义上的最大不同）。
我们需要考虑「不包含
，不包含
」、「不包含
，包含
」「包含
，不包含
」、「包含
，包含
」四种情况：
- 不包含
，不包含
：结合状态定义，可以使用
进行精确表示。
- 包含
，包含
：前提是
，可以使用
进行精确表示。
- 不包含
，包含
：结合状态定义，我们无法直接将该情况表示出来。 注意
只是表示「必然不包含
，但可能包含
」的情况，也就是说
其实是该情况与情况
的合集。 但是由于我们求的是「最大值」，只需要确保「不漏」即可保证答案的正确（某些情况被重复参与比较不影响正确性），因此这里直接使用
进行表示没有问题。
- 包含
，不包含
：与情况
同理，直接使用
表示没有问题。
就是在上述所有情况中取
而来，由于情况
被 情况
和 情况
所包含，因此我们只需要考虑
、
和
三种状态即可，其中最后一种状态需要满足
前提条件。
因此我们最后的状态转移方程为：
上述分析过程建议加深理解，估计很多同学能 AC 但其实并不知道 LCS 问题的状态转移是包含了「重复状态比较」的。
Java 代码：
class Solution {
public int maxUncrossedLines(int[] s1, int[] s2) {
int n = s1.length, m = s2.length;
int[][] f = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
if (s1[i - 1] == s2[j - 1]) {
f[i][j] = Math.max(f[i][j], f[i - 1][j - 1] + 1);
}
}
}
return f[n][m];
}
}
C++ 代码：
class Solution {
public:
int maxUncrossedLines(vector<int>& s1, vector<int>& s2) {
int n = s1.size(), m = s2.size();
vector<vector<int>> f(n + 1, vector<int>(m + 1, 0));
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 (s1[i - 1] == s2[j - 1]) {
f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
}
}
}
return f[n][m];
}
};
Python 代码：
class Solution:
def maxUncrossedLines(self, s1: List[int], s2: List[int]) -> int:
n, m = len(s1), len(s2)
f = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
f[i][j] = max(f[i - 1][j], f[i][j - 1])
if s1[i - 1] == s2[j - 1]:
f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1)
return f[n][m]
TypeScript 代码：
function maxUncrossedLines(s1: number[], s2: number[]): number {
const n = s1.length, m = s2.length;
const f = Array.from({ length: n + 1 }, () => Array(m + 1).fill(0));
for (let i = 1; i <= n; ++i) {
for (let j = 1; j <= m; ++j) {
f[i][j] = Math.max(f[i - 1][j], f[i][j - 1]);
if (s1[i - 1] === s2[j - 1]) {
f[i][j] = Math.max(f[i][j], f[i - 1][j - 1] + 1);
}
}
}
return f[n][m];
};
- 时间复杂度：
- 空间复杂度：
我是宫水三叶，每天都会分享算法题解，并和大家聊聊近期的所见所闻。
欢迎关注，明天见。