介绍

总而言之是时候利用暑假锻炼一下算法技术，一提算法面试就面露难色的情形总不能一直持续下去。本栏目面向有一定基础的编程爱好者，每天（如果up不鸽）分享并解析一道LeetCode中高难度题目（通常是hard）。有兴趣的小伙伴可以一起跟着做并且讨论解法。目前的教材是花花酱的Leetcode Problem List【1】.

适合人群：

有一定算法基础，但是还未能顺利通过笔试/面试，总觉得算法题目想不明白的你。

不适合人群：

算法入门级选手（一上来就做难题可能并不合适，建议首先专注简单/中等题目）

非常不适合人群：

算法竞赛选手（这种小儿科的问题完全是在浪费您的时间）

过往题目在这里！

最短公共超序列

题目看这里，leetcode第一零九二题，hard难度：
https://leetcode.com/problems/shortest-common-supersequence/

强烈建议读者自己先做（不过真的会有读者吗，笑），有任何问题欢迎在评论区讨论，up看到了会及时回复。做完了欢迎在评论区打卡～

解析

这题仍然是我们熟悉的动态规划题型，但有一点新意：我们在动态规划数组中直接存储最短公共超序列字符串，而非常见的布尔值或数值。这个做法虽然略显奇特，但同样有效。

此外，我们在这题中采用了“滚动数组”策略进行空间优化。这种策略的关键在于：首先写出常规的二维动态规划解法，然后将其改为仅使用两行存储计算结果，这样可以大大节省空间。在这个过程中，我们需要确保所有的行索引 i 都进行 mod 2 操作，以在每一步计算时保持对应的数据准确性。这种空间优化技巧在处理类似问题时非常有用。

思考乐园

此函数返回的结果是rows%2，为什么不是(rows-1)%2呢？欢迎将回答写在评论区。

时光流转，该幻灭的幻灭，该崩塌的崩塌，就算曾经的狂热化作泡影，我相信有些东西始终不变。所以，这首经典的《朝凤》送给即使遭遇了挫折却还依然向前奔跑的你。

请记住，非生来富贵，是天道酬勤！

教材链接

【1】https://zxi.mytechroad.com/blog/leetcode-problem-categories/