介紹

總而言之是時候利用暑假鍛煉一下算法技術(shù)，一提算法面試就面露難色的情形總不能一直持續(xù)下去。本欄目面向有一定基礎(chǔ)的編程愛好者，每天（如果up不鴿）分享并解析一道LeetCode中高難度題目（通常是hard）。有興趣的小伙伴可以一起跟著做并且討論解法。目前的教材是花花醬的Leetcode Problem List【1】.

適合人群：

有一定算法基礎(chǔ)，但是還未能順利通過筆試/面試，總覺得算法題目想不明白的你。

不適合人群：

算法入門級選手（一上來就做難題可能并不合適，建議首先專注簡單/中等題目）

非常不適合人群：

算法競賽選手（這種小兒科的問題完全是在浪費您的時間）

過往題目在這里！

最短公共超序列

題目看這里，leetcode第一零九二題，hard難度：
https://leetcode.com/problems/shortest-common-supersequence/

強烈建議讀者自己先做（不過真的會有讀者嗎，笑），有任何問題歡迎在評論區(qū)討論，up看到了會及時回復(fù)。做完了歡迎在評論區(qū)打卡～

解析

這題仍然是我們熟悉的動態(tài)規(guī)劃題型，但有一點新意：我們在動態(tài)規(guī)劃數(shù)組中直接存儲最短公共超序列字符串，而非常見的布爾值或數(shù)值。這個做法雖然略顯奇特，但同樣有效。

此外，我們在這題中采用了“滾動數(shù)組”策略進(jìn)行空間優(yōu)化。這種策略的關(guān)鍵在于：首先寫出常規(guī)的二維動態(tài)規(guī)劃解法，然后將其改為僅使用兩行存儲計算結(jié)果，這樣可以大大節(jié)省空間。在這個過程中，我們需要確保所有的行索引 i 都進(jìn)行 mod 2 操作，以在每一步計算時保持對應(yīng)的數(shù)據(jù)準(zhǔn)確性。這種空間優(yōu)化技巧在處理類似問題時非常有用。

思考樂園

此函數(shù)返回的結(jié)果是rows%2，為什么不是(rows-1)%2呢？歡迎將回答寫在評論區(qū)。

時光流轉(zhuǎn)，該幻滅的幻滅，該崩塌的崩塌，就算曾經(jīng)的狂熱化作泡影，我相信有些東西始終不變。所以，這首經(jīng)典的《朝鳳》送給即使遭遇了挫折卻還依然向前奔跑的你。

請記住，非生來富貴，是天道酬勤！

教材鏈接

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