介紹

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

適合人群：

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

不適合人群：

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

非常不適合人群：

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

過往題目在這里！

拆分子數(shù)組

題目看這里，leetcode第四百一十題，hard難度：
https://leetcode.com/problems/shortest-common-supersequence/

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

解析

在本題中，我們使用了一個二維的動態(tài)規(guī)劃矩陣，與之前的編輯距離類型題目有所不同。在編輯距離類型題目中，矩陣的行數(shù)和列數(shù)分別對應兩個字符串的長度。而在這個問題中，我們的矩陣的行數(shù)表示的是需要分割的子數(shù)組數(shù)量k，列數(shù)則對應原始數(shù)組nums的長度。另外，此類問題通常都是直接用問題構(gòu)造動態(tài)規(guī)劃矩陣。

此題的關鍵之一在于，當我們知道當前元素以及在i與j之前的dp值時，我們?nèi)绾吻蟮胐p[i][j]。常見的一種策略是試探所有可能的情況。也就是說，從當前元素開始向左，嘗試將數(shù)組分成兩部分。這里我們還添加了一個剪枝操作，那就是當我們持續(xù)往右邊的數(shù)組添加元素時，如果右側(cè)數(shù)組的總和已經(jīng)大于左側(cè)的，那么我們就不需要再繼續(xù)下去了，因為右邊數(shù)組的總和會一直是兩者之間的最大值。換句話說，我們在盡可能保證分組公平的情況下，盡早地結(jié)束了無謂的嘗試，從而提高了算法的效率。

思考樂園

第三層for循環(huán)內(nèi)有min和max，請問它們的作用分別是什么？歡迎將答案寫在評論區(qū)～

音樂推薦

今天去墨西哥餐廳用手指點了一道不認識的菜Chiles Rellenos，現(xiàn)場拿手機一查，原來是是墨西哥爆漿芝士辣椒。實際上整道菜里有卷餅，米飯，牛油果醬，奶油，豆泥，土豆絲，菜葉，玉米片，辣椒醬，以及一個很大的綠色辣椒，里面填充著像膠水的奶白色奶酪。味道其實還好，但是沒吃完，總覺得很膩。不過以上都和今天要推薦的歌曲沒有一絲一毫的關系，這里是來自安婧_Tiffany的One Last Kiss，送給也覺得去異國餐廳隨機點餐收到東西還挺合胃口真是幸運的你。說起來，是不是應該給無人問津的本欄目約個封面頭圖什么的呢......

教材鏈接

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