刻意练习之经典动态规划之最小路径三角形

开门见山

直接上题：

说，有个三角形triangle，请找出从顶点开始到底部的最小路径。

注意：每次只能向下移动，且每次移动只能去相邻的节点。

输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]

输出：11

解释：如下面简图所示：

自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

解题思路分析

既然是动态规划的刻意练习，那这个题目当然是用动态规划来进行解答。首先我们来分析一下为什么看到这道题，会第一时间想到动态规划。主要是因为这个题目有以下几个特点：

1.每一次的移动都和上一次有关系，比如当走到例题中的值为3的结点时候，下一步只能走到6或者5

2.题目要求的不是我们列出每一个步骤，而是求一个最小值。

符合以上两点我们首先要考虑的方法就是动态规划，既然选择了动态规划我们就把重心放在找规律（动态转移方程），和找初始值（边界条件）上了

第一步：我们定义一个结果数组，如果我们想要记录每个节点上的最小值，我们的结果数组就需要和参数的数组保持一致，才能很好的记录每个节点的最小值。

所以我们可以很容易的得出，我们需要先新建一个二维数组去做值的保存：

//创建一个和参数一样的二维数组
    const dep = triangle.length
    const result = new Array(dep);
    for (let i = 0; i < dep; i++) {
        result[i] = new Array(triangle[i].length);
    }
复制代码

第二步：我们找初始值，其实初始值一般都是第一个节点。以例题来说，我们的第一个初始值，也就是result的第0层的第一个的sum

 result[0][0] = triangle[0][0]
复制代码

第三步，找规律：

找规律像我们新手玩家熟练度不是很够的情况下，我们千万不要急~一下子找不出规律我们可从第二层开始看。
比如说，第二层到了3,4两个节点，这个时候我们可以很简单的求出在result中对应点的sum值是多少。
在3这个点上，从第一层加过来，和就是2+3=5,4这个点就是4+2=6，那么转换成语句的写法如下：

//节点3
result[1][0]=result[0][0]+triangle[0,0]
//节点4
result[1][1]=result[0][0]+triangle[0,0]
复制代码

如果题目到这里就已经结束了，需要我们找最小的路径，我们只需要返回Math.min(result[1][0],result[1][1])就好。

同理到了第三层的时候，我们可以用这个方法求出节点6和节点7两个节点的sum，但是关键就是值为5的这个节点，5这个结点的值既可以从节点3过来，也可以从节点4过来，那么是什么决定我们从哪个节点累加呢？是不是也是两个钟的最小值？

由此我们可以得出:

//结点5的最小值
result[2][1]=Math.min(result[1][1],result[1][0])+triangle[2,1]
复制代码

综上所述，我们尝试一下总结规律，可以得到以下3点：

1.每行的第一个只能从上一行的第一个累加过来

2.每行的最后一个只能从上一行的最后一个累加过来

3.每行的中间部分的最小和，是取上一行能走过来的点的和取最小值

第四步：把规律翻译成代码，我们用第一个循环去循环层数，下标为i,第二层循环去循环节点,下表为j,那么我们上面总结的三个规律可以翻译成一下代码：

规律一: result[i][0] = result[i - 1][0] + triangle[i][0]

规律二：

for (let j = 1; j < i; j++) {
            result[i][j] = Math.min(result[i - 1][j], result[i - 1][j - 1]) + triangle[i][j]
        }
复制代码

规律三：result[i][i] = result[i - 1][i - 1] + triangle[i][i]

最后我们就得到了result，只需要返回最后一层中的最小值Math.min(...result[result.length - 1])就是我们想要的结果了！

整体代码：

var minimumTotal = function (triangle) {
    //先创建一个二维数组保存每个位置的和
    const dep = triangle.length
    const result = new Array(dep);
    for (let i = 0; i < dep; i++) {
        result[i] = new Array(triangle[i].length);
    }
    result[0][0] = triangle[0][0]
    for (let i = 1; i < dep; i++) {
        //f[i][0]也就是每一行的第一个,只能从上一行的一个走过来
        result[i][0] = result[i - 1][0] + triangle[i][0]
        for (let j = 1; j < i; j++) {
            result[i][j] = Math.min(result[i - 1][j], result[i - 1][j - 1]) + triangle[i][j]
        }
        //f[i][i]也就是第i行的最后一个，只能从上一行的最后一个走过来
        result[i][i] = result[i - 1][i - 1] + triangle[i][i]
    }
    //这时候得到了一个二维数组result，表示每一次加到的num最小num值，题目需要的就是最后一排中的最小值
    return Math.min(...result[result.length - 1])
};
minimumTotal([[2],[3,4],[6,5,7],[4,1,8,3]])
复制代码

以上就是这道题目的70分解法（因为这种解法的空间复杂度高了点），个人觉得动态规划的第三步和第四步是动态规划的重难点。如何去攻破这个重难点，我想在智商不会突然变化的前提下，唯一能做的就是大量的刻意练习。
（一百分的解法请移步这里）

小声BB环节

周三的时候立了一个flag说要在周六看完《刻意练习》这本书并写一点读后感和一道经典的动态规划的题解之题解,总的来说目标完成了一半（因为书还没看完）~

之前看《断舍离》这本书，发现这类书都有一个特点—整本书就是为了跟你讲书名。用不同的角度和例子，从第一章讲到最后一章去和你灌输这个想法。这就造成了一个很差的阅读体验。大概就是你读完第一章第二章你就差不多知道后面的章节大概是将些啥，可能是换了一个人的故事跟你重复阐述这个道理。

《刻意练习》大概是对一万个小时定律表达了不同的观点，认为一个成为一个行业的翘楚或者说把一个技能修炼到大师水平，一万个小时定律概括的有点笼统，重要的还是跳出舒适圈的刻意练习，书中提到的绝对音高和对数字的快速记忆的例子都很好的论证了刻意练习的强大和重要性。再给我一周的时间，我一定好好把这本书看完，到时候在下一篇文章中，再来和大家好好聊聊~

还有和大家分享一件事就是：我最近找到了一个很好的早起的方法。就是在前一天下一个顺风车单，然后提前支付，给自己一个早期的理由~已经连续四天早起成功！做这件事的好处有两点：

1.早起可以腾出早上一大段完整时间，很适合做算法题和理思路！

2.顺风车车主都很有故事，和他们聊天真的很有意思！

3.早起一天的精气神和晚起真的不一样，真的真的不一样！前提是你晚上十二点之前一定要睡觉！

最后的最后，如果你看到这里，请给我文章点个赞或者留下你的评论或指正~

下期大概就要开始刷一下滑动窗口这个精英怪