效果如图：预览地址：https://sl1673495.github.io/d...可以看出，贪心算法只求局部最优解（只考虑在当前图片中找到一个最优解），所以最终左右两边的高度差比较大，局部最优解很难变成全局最优解。回到文章开头的图看看，对于同一个图像数组，预览图像中的高度差很小，是怎么做到的？动态规划和局部最优解对应的是全局最优解，提到全局最优解，就很难不想到动态规划算法。它是寻找全局最优解的利器。如果你还没有学过动态规划，建议你看看海兰老师的《理解动态规划》一文。这篇文章也给我介绍了最基本的动态规划。动态规划中有一个非常著名的问题：“01knapsackproblem”，题目的意思是这样的：有n个物品，它们有自己的体积和价值，有一个给定容量的背包，怎么放它放入背包中价值总和最大的物品？关于01背包问题的解法，网上好像没有多少好的教程。推荐看波波老师趣味算法面试中的算法思维第九章从真题到思考。它会很仔细地解释背包问题。算法思维得到了很大的提升，这门课的其他部分也非常非常优秀。我也在自己维护的方案库中对老师01背包方案的js版进行了重写。那么01背包问题和这个瀑布算法有什么关系呢？这个思路确实不好找，但是我们仔细想想，假设我们有一个3个图像高度的数组[1,2,3]，我们如何把它转化为一个01的背包问题呢？由于我们要得到的是图片总高度的一半，即(1+2+3)/2=3，那么我们现在有一个容量为3的背包，由于我们把它放在leftcolumn图像高度需要小于总高度的一半，并且要装入背包的物品的总重量和高度相同[1,2,3]。那么这个问题就转化为，在容量为3的背包中，尽量从重量为[1,2,3]，值为[1,2,3]的物品中挑选出尽可能多的物品集合总价值最大的物品被装入背包。即总高度为3，在高度为[1,2,3]的图片中，尽可能挑出和最大但小于3的图片集合，放入数组中。可以分析出状态转移方程为dp[heights][height]=max(//选择当前图片放到列currentHeight+dp[heights-1][height-currnetHeight],//不选中selectthecurrentpicturedp[heights-1][height])注意这里的纵坐标命名为heights，意思是“可选图片的集合”。例如dp[0]表示只考虑第一张图片，dp[1]表示既考虑第一张图片又考虑第二张图片，以此类推。二维数组结构我们构建的二维dp数组的纵坐标y为：当前可以考虑的图片，比如dp[0]只考虑下标为0的图片，dp[1]考虑下标为0的图片。再考虑下标为1的图片，以此类推，取值范围为0~图片数组长度-1。横坐标x为：拼接时可拼出的最大高度maxtotalheight是y与当前考虑的图像集合，和当前使用的图像下标集合索引，取值范围是0~height的一半。拆解小问题，以四张图片[1,4,5,4]的高度为例。高度的一半是7，肉眼可以看出离7最近的子数组是[1,5]。让我们看看动态规划是如何找到这个结果的。我们先来看0的纵坐标，也就是只考虑图1的情况：首先尝试获取高度1：我们知道图片1的高度刚好是1，所以填入dp[0]的值此时的[0]为{max:1,indexes:[0]}，也就是说总高度还剩1，只考虑图片1，我们的最优解是选择第一张图片。Compositeheight2~7:由于目前只能选1张，最优解只能是选第一张图，都是{max:1,indexes:[0]}。Height1234567图1(h=1)1111111这一层在动态规划中称为基本状态，是最小的子问题，以下纵坐标不考虑多张图片，但只考虑单张图片，所以一般来说，会循环单独解决。这里我们还需要考虑第一张图片的高度大于我们需要的总高度的情况。在这种情况下，我们需要将max设置为0，选中的图片项也为空。letmid=Math.round(sum(heights)/2)letdp=[]//基本状态只考虑第一张图dp[0]=[]for(letcap=0;cap<=mid;cap++){dp[0][cap]=heights[0]>cap?{max:0,indexes:[]}:{max:heights[0],indexes:[0]}}有了第一层的基本状态后，我们就可以开始考虑多张图片的情况了。现在我们来到1的纵坐标，即求图1和图2时的最优解：height1234567picture1(h=1)1111111Picture2(h=2)这时候问题就变得有点复杂了。在多张图片的情况下，我们可以有两种选择：选择当前图片，那么假设当前要合并的总高度为3，当前图片高度为2，剩余高度为1。此时时间，我们可以利用剩余高度在“上一个纵坐标”中找到“只考虑前几张图片”的情况，高度为1时的最优解。并记录下当前图片的高度+的最优解前面图片的剩余高度是max1。如果不选择当前图片，则直接到“只考虑前面几张图片”的上一个纵坐标，求当前高度的最优解，记为max2。比较max1和max2，找出较大的值，记录为当前状态下的最优解。有了这些前置知识，我们继续分解这个问题。当纵坐标为1时，我们可以选择的图片为图1和图2：高度1：由于图2的高度为2，相当于超出了容量，所以这种情况下不选择图1而不是图2，所以dp[1][0]可以直接使用dp[0][0]的最优解，即{max:1,indexes:[0]}。组合高度2：选择图片2，图片2的高度为4，可以组合的高度为4，已经超过了当前要组合的高度2，所以不能选择图片2。不选图2，只考虑图1时在最优解数组dp[0]中求高度为2时的最优解：dp[0][2]，直接用，即{max:1,indexes:[0]}这种情况下，我们只能选择图片2，不能选择图片1。{max:1,indexes:[0]}省略高度3~4的情况，因为我们得到的结果和Mino是一样的height2.Compositeheight5:当高度为5时更有意思：选择图片2，图片2的高度为4，可以组合的高度为4，此时剩下的高度为1，然后只考虑最优图片1在解数组dp[0]中寻找高度为1时的最优解dp[0][1]，发现结果为{max:1,indexes:[0]}，后将这两个高度值相加4和1超出高度没有限制，所以得到最优解：{max:5,indexes:[0,1]}不要选择图2，当求最优解最优解中的高度为5图1的ution数组：dp[0][5]，直接使用，即{max:1,indexes:[0]}显然，在选择图2的情况下，可以做出的高度为更大，所以dp[1][2]最优解选择{max:5,indexes:[0,1]}仔细理解，相信大家可以看到动态规划的过程，从最小的子问题开始只考虑图1，先求最优解，然后用子问题的最优解推更大的问题去考虑图1和图2，同时考虑图1、2和3的最优解。画出的dp状态表[1,4,5,4]问题：可以看到和我们刚才推导的结果是一致的。在考虑图1和图2的情况下，组合高度为5，即dp[1][5]位置的最优解为5。右下角的dp[3][7]是考虑所有图片时高度为7时的全局最优解。dp[3][7]的推理过程如下：用最后一张高度为4的图片，加上高度为7-4=3时前三张图片的最优解，即dp[2][3]，得到结果4+1=5。代替最后一张，直接取前三张图片在高度为7时的最优解，即dp[2][7]，得到结果6.比较这两个的值，得到最优解6。至此我们就完成了整个动态规划过程，在考虑所有图片的情况下，得到最大高度为7时的最优解：6.需要的两张图片的下标为[0,2]，对应高度为1和5。给出代码：//尝试选择高度最接近图像总高度一半的元素letdpHalf=(heights)=>{letmid=Math.round(sum(heights)/2)letdp=[]//基本状态只考虑第一张图的情况dp[0]=[]for(letcap=0;cap<=mid;cap++){dp[0][cap]=heights[0]>cap？{max:0,indexes:[]}:{max:heights[0],indexes:[0]}}for(letuseHeightIndex=1;useHeightIndexusePrevHeightMax){dp[useHeightIndex][cap]={max:useThisHeightMax,indexes:useThisHeightPrevDp.indexes.concat(useHeightIndex),}}else{dp[useHeightIndex][cap]={max:usePrevHeightMax,索引:usePrevHeightDp.indexes,}}}}returndp[heights.length-1][mid]}有了一侧数组后，我们只需要找到数组中的另一半，就可以渲染到屏幕的两列：this.leftImgIndexes=dpHalf(imgHeights).indexesthis.rightImgIndexes=omitByIndexes(this.imgs,this.leftImgIndexes)作用：优化1由于纵轴每一层的最优解只需要参考上一层节点的最优解，所以只需要保留两行来确定“上一行”的位置"通过判断除以2并取余数。此时空间复杂度为O(n)。优化2由于每个参考值只需要取上一行的值和当前位置的左边（因为减去当前高度后，剩余高度的最优解一定在左边），所以dp数组只能保留一行，且问题切换为从右向左求解，求解过程中不断覆盖当前值，不影响下一次求解。此时空间复杂度为O(n)，但占用的空间进一步减少。而且这种情况下，时间复杂度也可以进行优化，因为优化之后，是对当前高度的最优解进行倒序遍历，那么当发现最优解的高度小于图片的高度时currentlyunderconsideration，表示在这个解中不可能考虑当前的图片。这时左边高度的最优解一定是“上一行的最优解”。代码地址预览地址完整代码地址总结算法思路在前端的很多应用中还是可以看到的。本文只是为了展示动态规划在求解最优解问题上的威力，并不代表该算法适用于生产环境（实际表现很差）。在实际场景中，我们可能肯定需要最优解，但只需要左右两边的高度差不要太大即可。在这种情况下，一个简单的贪心算法就完全足够了。在业务工程中，我们需要结合当前的人力资源、项目周期、代码可维护性、性能等方面来选择最适合业务场景的方案，不一定要找到最优方案。但是算法对于前端来说还是很重要的。如果你想写出没有错误的代码，你可以很容易地想出一种方法来优化复杂的业务场景的复杂性。学习算法是一个很好的方法，这也是一个工程师必备的素质。推荐我维护一个LeetCode题解仓库，里面会根据标签记录一些平时刷题时遇到的经典题，也会经常更新bobo先生的Leetcode算法课程Algorithm中提到的各个类别的经典题，将他的C++解决方案重写为JavaScript解决方案。欢迎关注，我会持续更新。参考文章理解动态规划，玩转算法面试全面提升算法思维，从真题到思维??谢谢大家1.如果本文对您有帮助，请点赞支持。您的“喜欢”是我创作的动力。2、关注公众号“前端从进阶到入学”加我为好友，我拉你进“前端进阶交流群”，大家一起交流，共同进步。