介绍

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

适合人群：

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

不适合人群：

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

非常不适合人群：

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

过往题目在这里！

拆分子数组

题目看这里，leetcode第四百一十题，hard难度：
https://leetcode.com/problems/shortest-common-supersequence/

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

解析

在本题中，我们使用了一个二维的动态规划矩阵，与之前的编辑距离类型题目有所不同。在编辑距离类型题目中，矩阵的行数和列数分别对应两个字符串的长度。而在这个问题中，我们的矩阵的行数表示的是需要分割的子数组数量k，列数则对应原始数组nums的长度。另外，此类问题通常都是直接用问题构造动态规划矩阵。

此题的关键之一在于，当我们知道当前元素以及在i与j之前的dp值时，我们如何求得dp[i][j]。常见的一种策略是试探所有可能的情况。也就是说，从当前元素开始向左，尝试将数组分成两部分。这里我们还添加了一个剪枝操作，那就是当我们持续往右边的数组添加元素时，如果右侧数组的总和已经大于左侧的，那么我们就不需要再继续下去了，因为右边数组的总和会一直是两者之间的最大值。换句话说，我们在尽可能保证分组公平的情况下，尽早地结束了无谓的尝试，从而提高了算法的效率。

思考乐园

第三层for循环内有min和max，请问它们的作用分别是什么？欢迎将答案写在评论区～

音乐推荐

今天去墨西哥餐厅用手指点了一道不认识的菜Chiles Rellenos，现场拿手机一查，原来是是墨西哥爆浆芝士辣椒。实际上整道菜里有卷饼，米饭，牛油果酱，奶油，豆泥，土豆丝，菜叶，玉米片，辣椒酱，以及一个很大的绿色辣椒，里面填充着像胶水的奶白色奶酪。味道其实还好，但是没吃完，总觉得很腻。不过以上都和今天要推荐的歌曲没有一丝一毫的关系，这里是来自安婧_Tiffany的One Last Kiss，送给也觉得去异国餐厅随机点餐收到东西还挺合胃口真是幸运的你。说起来，是不是应该给无人问津的本栏目约个封面头图什么的呢......

教材链接

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