menu

Leetcode Mr.How知其所以然之120_Triangle主题模块

Leetcode Mr.How知其所以然之120_Triangle主题模块

原创文章，版权所有，搬运文章，转发请注明polyaD，原文链接https://polyad.github.io/tags 如有任何问题或疑惑，请在后面留言或者发邮箱留言polyaluthor@gmail.com，加微信polyad或者qq数学算法开发10群 282642152进行探讨,请备注：Mr.How。

前言
  您好，欢迎来到我的引导学习记录笔记，我是polayD, Mr.How先生。本系列依据《怎样解题》，George Polya的方法以及知其所以然模式启发，进行拓展而成。希望在这里，您能找到引导式学习的快乐，逐步建立与形成自己的知识同化模式，摆脱碎片化信息的烦扰，掌握快速学习与深度知识系统化的技能，期待与您共同进步。
  信息碎片化的时代，随波逐流我们将一无所获，特别是当没有形成系统垂直化的知识模块，很多时候我们只能人云亦云，面对海量信息，无法判别重要性，相关性，有效性，普通的个人很难在信息洪流中找到自己的定位。深度式的知其所以然的引导式学习，可避开信息碎片化旋涡，同时突破信息茧房的束缚。下面波利亚将引领您，进入一个这个基础主题模块的海洋，带上自己的定位导航，抓紧好奇心的船舵，扬帆深入得在这片海洋里探索，前进，自我迭代进化。
**理念与标准设定迭代模块**
I.理念迭代：
1.缝合现实与理论的鸿沟。
2.缝合理论主题与练习的鸿沟。
3.认知升级：掌握方法论比掌握知识点更重要。
4.设立量化目标：标准框架与计划实施作业，建立模块化迭代。
5.潜意识出发平缓引导：第一人称为主，进行自我提问与引导，主要是让自我潜意识有参与感。
6.一根针插到底的解决问题：只要内心存在疑问，就应该把问题写入问题列表，随便再进行解读。彻底明白一个系统模块，胜过离散的弄清单个问题。
7.信息资源发散式归集：以此问题为核心支点，散发结合所有可能收集到的认知，整合解读，不唯教科书论，不唯单一信息来源论。尽量多查找一手资源。
8.问题全流程迭代：现实3D场景->发现问题->设立标准->提出问题->描述问题信息->解决问题->实践验证->抽象化->理论化->一般化->主题框架化->重新应用于新的3D场景。
潜意识（集体潜意识->个人潜意识）->哲学智慧->数据->信息->知识->洞见->智慧->影响力->潜意识（集体潜意识->个人潜意识）。 潜意识（集体潜意识->个人潜意识）->现实场景（3D数据，2D数据，1D数据）->发现问题->设立标准->提出问题->描述问题信息->问题引导列表->解决问题->可操作手册工具箱->实践验证->抽象化->理论化->一般化->主题框架化->重新应用于新的3D场景->潜意识（集体潜意识->个人潜意识）
9.导航路径：同类主题区别层面->理论层面->系列问题归集层面->实际问题解决层面 10.细节是魔鬼，细节决定了专业的高度
11.实现从0开始逐步构建到框架，从迭代框架实现知识的同化
12.算法是建立的数据结构上的操作，可以用不同的数据结构实现相同的结果
13.放下书本与答案，自我构建从0开始推导，用自己的理解写出来，标准是每一个小模块都是灵活使用。
14.先攻克最难的部分，再往易处走，如下山猛虎。带着问题，不断解析。最难部分要从易处着眼，从具体到逐步抽象，不断提出问题四面八方进行敲击，直到牢固。
15.主题系统如果是固化的，那说明只是在记忆，而不是理解与彻底掌握，必将一无所有。不以任何书本为准，而是以自我的知识构建为准，所有的资源都是为了自我知识构建服务，从第一性原理（从0）开始构建整个知识系统大厦。

II.标准与实施设定迭代：

 首先，做什么事之前，先要设定一下我们的小目标， 我们的整体导航路径： 1.主题解析，找出这个领域的最难的地方，先难后易，深入浅出，案例拆解，举一反三。
2.主要解决两个问题：如何思考这个问题？如何使用这个解决问题？
3.尽可能所有收集参考资料，实践以后，再全部用自己的语言进行复述回答，将思路，事无巨细的写出来，特别是关键节点。
4.陆续将提供中英文版本。
5.问题解决同化迭代模式：理念与标准设定迭代模块，计划与实施迭代模块，路径框架迭代模块，问题引导列表分析迭代模块，执行分析步骤迭代模块，动画与代码实现迭代模块，方法工具归集迭代模块，反思批判迭代模块，十字定位迭代模块，意义与主题迭代模块，拓展应用迭代模块。
6.知识点主题模块同化迭代模式：理念与标准设定迭代模块，计划与实施迭代模块，路径框架迭代模块，意义背景迭代模块，十字定位迭代模块，问题引导列表分析迭代模块，区别迭代模块，反思批判迭代模块，拓展应用迭代模块。
计划与实施迭代模块
 

**路径框架迭代模块**

问题引导列表分析迭代模块
问题模块
问题思路与分析模块 完整调试代码实现：C++,python,java,PHP,GO,javascript模块
问题记录列表解析模块

**问题引导列表分析迭代模块**

  • I 如何才算对这个问题知其所以然？
  • 弄清问题 1．未知的是什么?已知的是什么？条件是什么?满足条件是否可能? 要确定未知的,条件是否充分?或者它是否不充分?或者是多余的?或者是矛盾的? 2．画张图,并引入适当的符号。 3．把条件的各部分分开,并把它们写下来。
  • 拟订计划 1．考虑以前是否见过它? 是否见过相同的问题而形式稍有不同? 我是否知道一个可能用上的规律? 2．考虑具有相同未知的或相似未知的熟悉的问题。
    3．能否利用它的结果或方法?为了利用它,是否引入某些辅助元素? 4．能否用不同的方法重新叙述它? 5．回到概念上去。
    6．如果我不能解决所提出的问题,可先解决一个与此有关的问题。
    7．是否利用了所有的已知的?是否利用了所有条件？是否考虑了 包含在问题中的所有必要的概念?
  • 实现计划 1．实现我的求解计划,检验每一步骤。
    2．我能否清楚地看出这一步骤是正确的? 我能否证明这一步骤是正确的? 我能否说出我所写的每一步的理由？ 回顾重要
    从理解开始，它的每一个细节都应该是完整而正确的，
    从各个方面考虑这个解，找出与我已有知识之间的联系。
    考虑解的细节，并尝试使它们尽可能地简单；
    总结我解题的方法，并且尝试把它用于其他问题。
    1． 能否检验这个论证?
    2． 你能否用别的方法导出结果?
    3． 能不能一下子看出它来?
    4． 能不能把这结果或方法用于其他问题?
  • 揣摩问题
    1． 为什么要这样（为什么这是好的）？
    2． 为什么不是那样（有其它做法吗？有更好的做法吗？）？
    3． 这样做是最好的吗？（为什么？能证明吗？）
    4． 这个做法跟其它的什么做法有本质联系吗？
    5． 这个跟这个的区别是什么？
    6． 问题的本质是什么？
    7． 这个做法的本质又是什么？
    8． 到底本质上是什么东西导致了这个做法如此？
    9． 与这个问题类似的还有其它问题吗？（同样或类似的做法也适用吗？）
  • II.这个问题类型
    • 1.这个问题通用步骤及公式
    • 2.这个问题类别区分
    • 3.这个问题归集
  • III.问题实际项目案例实施

**问题模块** 120.Triangle

English version:  
Given a triangle array, return the minimum path sum from top to bottom.  

For each step, you may move to an adjacent number of the row below. More formally, if you are on index i on the current row, you may move to either index i or index i + 1 on the next row.  

Example 1:  

Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]  
Output: 11  
Explanation: The triangle looks like:  
   2  
  3 4  
 6 5 7  
4 1 8 3  
The minimum path sum from top to bottom is 2 + 3 + 5 + 1 = 11 (underlined above).  
Example 2:  

Input: triangle = [[-10]]   
Output: -10   



中文版本:
给定一个三角形形状的多维数组，从上到下，找到一条路径，使他们沿着这条路径的所有值的和最小。  

注意： 每一步移动，只能相邻位置移动，你每次当能在当前位置同层移动或向下移动
示例1：
输入：三角形状的多维数组 = [[2],[3,4],[6,5,7],[4,1,8,3]]  
   2  
  3 4  
 6 5 7  
4 1 8 3  
输出：因为这条路径 2 + 3 + 5 + 1 = 11 得到路径和的最小值


示例2：
输入：triangle = [[-10]]   
输出：-10

**问题思路与分析模块**

  • 问题引导解析 - 弄清问题 1．未知的是什么?已知的是什么？条件是什么?满足条件是否可能? 要确定未知的,条件是否充分?或者它是否不充分?或者是多余的?或者是矛盾的?

    • 依次回答以上问题，未知数：沿着经过的路径使和最小。 已知：三角形的多维数组，格子盘的每个格子的数组索引，每个格子上的值，值为正或负数。条件：每次向同层的相邻下或相邻的向下移动。条件可以满足。条件充分，可达到目标：可以从左上到右下找到多条路径，从多条路径中选择一条最小的和值即可。充分，不多余，不矛盾。

    2．画张图,并引入适当的符号。

    • 树形的多维数组,每个格子上的值。画一条路径得到一个和值。将路径推向临界值。

    3．把条件的各部分分开,并把它们写下来。

    • 相邻同层左右移动或向下移动

  • 拟订计划 1．考虑以前是否见过它? 是否见过相同的问题而形式稍有不同? 我是否知道一个可能用上的规律?

  • 见过，符合递归特征，重叠子，问题不断缩小，数学归纳法。动态规划，符合多阶段，重叠子，最优化，无后效性的特征

2．考虑具有相同未知的或相似未知的熟悉的问题。

  • 考虑到有相同未知的熟悉的问题。

3．能否利用它的结果或方法?为了利用它,是否引入某些辅助元素?

  • 可以利用它的方法：可以用多维数组表示，。目标是树形多维数组的和值使之最小，先表示，这个和值，再选择使这个值最小的和。

4．能否用不同的方法重新叙述它?

  • 找条最值路径从树形的多维数组上

5．回到概念上去。

  • 递归的特征概念，动态规划的特征概念

6．如果我不能解决所提出的问题,可先解决一个与此有关的问题。

  • 可以，可以先实现递归

7．是否利用了所有的已知的?是否利用了所有条件？是否考虑了 包含在问题中的所有必要的概念?

  • 是的,查找他人已经做到的方法，能过潜意识打通，并理解。

  • 语言思路详细描述
    • 实现计划 1．实现我的求解计划,检验每一步骤。
      ``` 动态规划解题框架：
      DP问题通用解题框架引导
      我能否判断这是个动态规划问题？

    • 可以判断是个动态规划问题 1.是否有接触过类似题目？ 2.是否多阶段，有重叠子，最优子结构，无后效性。 阶段之间：多个途径到达;重叠子:可以用递归;最优子结构：需要做最优选择;无后效性：可备忘录式优化。

    • 符合动规特征，需要多个多段到达目标;可以使用递归，需要在多个步骤之间进行最优化选择，当前状态只由前两个状态决定。
      3.先用递归算法解决，再考虑用动态规划逐步优化。动态规划流程：递归的暴力解法 -> 带备忘录的递归解法 -> 非递归的动态规划解法。

    • 1.暴力递归版本，源自于数学归纳法，主要解决第n项与其他项的关系式，确实边界。2.带备忘录的递归解法。3.把这个「备忘录」独立出来成为一张表，完成「自底向上」的推算。

    能否按照递归步骤实现？

    • 递归规划版本，源自于数学归纳法，属于数学证明。
      递归规划的四大步骤：递归函数定义状态->递归函数关系定义状态之间的关系->完整初始状态的安全边界->画图优化 第一步骤：定义递归函数的含义：状态定义 格子盘m*n,定义某个格子的位置用最小和填充。
      设定某位置，行为i，列为j。
      定义grid[i][j]为格子上的输入的值。
      递归函数定义状态：路径值的最小和。grid[i][j]为是本位置的值加上，判断从左前一个位置路径最小和或右上一位置路径最小，它们之间比较值的结果。
      若要求得左前一个位置的路径值的最小和 与右上一位置的路径值的最小和，则需要用递归实现。为重叠子结构。选择其大小，即为最优子结构。

    第二步骤：画图找出函数之间的关系式：递归函数定义状态之间的关系
    利用历史数据来推出新的函数值关系，即找出递归函数项之间的关系式。

    第三步骤：找出初始值，确定安全边界
    有了初始值，并且有了函数之间的关系式，就可以得到 f(n) 的值。
    理念状态有两个制约条件下的关系式：本格子值+(可选的左前，上前)的最值。 初始值：
    少一个条件: 最左边路径值，只与上一个路径值有关；最上边路径值，只与左边路径值有关。
    少二个条件：确定初始值f(0)。

    第四步骤：画图优化
    时间与空间复杂度优化

    能否按照动态规划步骤实现？

    • 动态规划版本，源自于运筹学优化理论。
      动态规划的四大步骤：状态定义->状态之间的关系->初始状态的安全边界->画图优化
      第一步骤：定义数组元素的含义

    第二步骤：画图找出数组元素之间的关系式

    第三步骤：找出初始值，确定安全边界

    理念状态有两个制约条件下的关系式：本格子值+(可选的左前，上前)的最值。
    少一个条件: 最左边路径值，只与上一个路径值有关；最上边路径值，只与左边路径值有关。
    少二个条件：确定初始值f(0)。

    第四步骤：画图优化
    空间复杂度优化
    二维矩阵优化成一维矩阵
    画二维 dp 的矩阵图，然后看元素之间的值依赖。 ```

    2．我能否清楚地看出这一步骤是正确的? 我能否证明这一步骤是正确的? 我能否说出我所写的每一步的理由？

  • 语言实现代码描述
    • 暴力递归实现代码描述
    • 带备忘录的递归解法实现代码描述
    • 独立成表的动态规划实现代码描述
    • 空间优化的动态规划实现代码描述
    • 多种数据结构动态规划实现代码描述
  • 伪代码
  • 动画每步过程实现

**完整调试代码实现：C++,python,java,Go,javascript,PHP模块**

  • 暴力递归实现
  • 带备忘录的递归解法实现
  • 独立成表的动态规划实现
  • 空间优化的动态规划实现
  • 多种数据结构动态规划实现

更新潜意识系统模块* 理想化->极值化
具体化-抽象化

*升级思想思维系统 ** 如果将多维数组转成二维数组表示？

  • 将其转为一个二维表格，与64问题做相同处理，向左填充，其余格子填-，先用转化方法。

  • 如何将三角数组，转为二维表格？转化成标准输出格式。其他解决方式，只需要更新关系式。

  • 特征：求取约束条件下最小路径的题。将三角形数阵可以抽象成一个二维矩阵 。转换成自底向上的求解思路。

*归集工具方法系统 ** 判断是否可以用动态规划？

  • 是否可变小问题规模，是否需要做条件选择？是否当前状态只与最近的相关？
    扫描技术，自上而下，自下而上？

  • 自下而上 for(int i=length-2;i>=0;i–) 自上而下，顺序扫描

**理清概念区别系统 模块**

**整理案例问题系统模块**

  • 问题全流程迭代拓展 现实3D场景->发现问题->设立标准->提出问题->描述问题信息->解决问题->实践验证->抽象化->理论化->一般化->主题框架化->重新应用于新的3D场景。
    格子盘找路径可以还原到现实生活中的3D场景：贪吃蛇游戏路径规划，

**经典好书与资源集**

#参考资料
—–
一级资料文献与书籍及重要作者
文献：
书籍：
博客：Leetcode Problem 64: Minimum Path Sum
Min Cost Path | DP-6 https://www.fatalerrors.org/a/0tp10jk.html
Dynamic Programming: 120. Triangle
论坛：
视频：

二级资料：他人加工且有观点及大众资料
博客： 论坛：
视频：

返回顶部

评论：

技术文章推送

知其所以然主题模块分享

微信搜索公众号: How先生polyad
wechat 微信公众号：How先生polyad