menu

Leetcode Mr.How知其所以然之64_Minimum_Path_Sum主题模块

Leetcode Mr.How知其所以然之64_Minimum_Path_Sum主题模块

原创文章，版权所有，搬运文章，转发请注明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.问题实际项目案例实施

**问题模块** 64. Minimum Path Sum

English version:
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Example 1:
Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.
Example 2:

Input: grid = [[1,2,3],[4,5,6]]
Output: 12
 

Constraints:

m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 100


中文版本:
给定一个m*n的格子盘，用非负数值填充，从左上到右下，找到一条路径，使他们沿着这条路径的所有值的和最小。  

注意： 你每次只能向下或右移动
示例1：
输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解析：因为这条路径 1 → 3 → 1 → 1 → 1  得到路径和的最小值

示例2：
输入：grid = [[1,2,3],[4,5,6]]
输出：12
解析：

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

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

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

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

    • m*n的格子盘,格子盘的每个格子的数组索引,每个格子上的值。画一条路径得到一个和值。将m,n推向临界值。

    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)。

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

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

    • 动态规划版本，源自于运筹学优化理论。
      动态规划的四大步骤：状态定义->状态之间的关系->初始状态的安全边界->画图优化
      第一步骤：定义数组元素的含义
      dp[i] 是代表什么意思？
      第二步骤：画图找出数组元素之间的关系式
      利用历史数据来推出新的元素值，即找出数组元素之间的关系式。
      第三步骤：找出初始值，确定安全边界
      有了初始值，并且有了数组元素之间的关系式，就可以得到 dp[n] 的值。
      边界确定： 理念状态有两个制约条件下的关系式：本格子值+(可选的左前，上前)的最值。
      少一个条件: 最左边路径值，只与上一个路径值有关；最上边路径值，只与左边路径值有关。
      少二个条件：确定初始值f(0)。

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

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

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

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

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

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

二维型的DP,可以用此框架：

*升级思想思维系统 ** 递归：递归是递归函数，指的是函数里面嵌套函数，函数嵌套会导致空间复杂度指数级别增长。 函数的输入数据标准化，需要在完成之前实现。

NT_MAX:返回此值，在递归中比返回0更好，防止溢出。

难点：数学上解决，算法上解决，选择数据结构，优化空间。

多函数包装技术：

f(A)->recursion f(B)->recursion f(B)

尾递归实现技术：

带备忘录技术：

*归集工具方法系统 ** 二维数组存储值技术： 格子盘用二维数组表示 。
数组下标创建新的二维数组技术： 现有数组得到下标，创建一个新的大小的二维数组，用此二维数组的项表示结果。
数组边界安全确认技术：

**理清概念区别系统 模块** 状态与阶段：状态与阶段是同义词，多状态即多阶段。
转移：从一个阶段到下一个阶段的实现过程。
状态阶段方程：从一个状态变换到下一个状态的函数关系。 剪枝：即递归前的做的选择，代码实现，max,min,sum等。
递归的复杂度：来源于空间复杂度，递归嵌套导致内存问题。

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

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

如何从0开始写出解决思路全流程？

  • 递归，符合规则条件下，理想化的位置，与前项的关系。逐步减少规则，确实边界，与前项的关系，第一项，直接初始化。

  • DP,填充二维数组。先填理想条件与位置下，再填边界，若是第一格，直接返回结果，初始化。 为何选用数组这种数据结构表示格子盘？可以用其他数据格式吗？

  • 算法是基于数据存储的操作，格子盘一般可以用数组进行有效的表示。
    暴力递归是否所有的可能性都会计算？再选择最值方案？

  • 暴力递归也没有计算所有的结果，而是在递归过程中进行了剪枝。
    格子盘的i,j索引应该从0还是从1开始？
    -> 从0开始 递归函数与数组的关系?

  • 递归函数的定义
    递归函数与n的关系，递归函数与参数下标的关系？

  • f（n）,f(n-1),f(n-2) *** ,f(1)

  • 拓展与相关 能否给出这个格子盘的路径和所有可能的解？

  • 即不做最值比较，直接返回一个数组，将值装入即可。 能否给出这个格子盘的路径和所有可能的其他最值？

  • 可以，最大路径和，最小路径和。
    能否输出这条最值路径?

  • 可再增加一个数组，每得到一个最值，就装入这个数组。然后输出
    一个函数是否可以输出多个结果？

  • 一般一个函数返回一个结果，若有需要可以技术上解决。不同结果装入不同函数，或者装入一个数组，返回数组即可。
    如何格子盘的值有负数，如何处理？

  • 需要选择前判断是否为负数。
    递归中grid二维数组到底是代表的是输入的二维数组，还是定义的第n项?

  • 一个二维数组 能否列出一维数组与二维数组的操作？

二维数组下标

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

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

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

返回顶部

评论：

技术文章推送

知其所以然主题模块分享

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