弗洛伊德算法作为求最短路径的经典算法，其算法实现相比迪杰斯特拉等算法是非常优雅的，可读性和理解都非常好。
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的「下降路径」的「最小和」。
在动态规划最短路径经常提及，在上几篇介绍过相关的最短路径的问题，介绍过使用Dijkstra算法去求解，但是Dijkstra算法是基于贪心算法，按路径长度递增的次序一步一步并入来求取，算法效率低效。
现在给你输入一个二维数组grid，其中的元素都是非负整数，现在你站在左上角，只能向右或者向下移动，需要到达右下角。现在请你计算，经过的路径和最小是多少？
链接：64. 最小路径和 - 力扣（LeetCode） (leetcode-cn.com)
这道题目作为算法题出现，最早可以追溯到 1994 年的 IOI（国际信息学奥林匹克竞赛）的 The Triangle。
如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。
首先我们分析题目，要找的是 最小路径和， 这是个啥意思呢？假设我们有一个 m * n 的矩形 ：[[1,3,1],[1,5,1],[4,2,1]]
动态规划是求解“最小路径”的常用方法之一，LeetCode上关于“最小路径”的题目如下：
题目描述 给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
动态规划（Dynamic Programming）是动态规划是分治思想的延伸，通俗一点来说就是大事化小，小事化无的艺术。在将大问题化解为小问题的分治过程中，保存对这些小问题已经处理好的结果，并供后面处理更大规模的问题时直接使用这些结果。
在上一篇中，我们通过分析，顺利完成了“三角形最小路径和”的动态规划题解。在本节中，我们继续看一道相似题型，以求能完全掌握这种“路径和”的问题。话不多说，先看题目：
给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
给定一个数字三角形，找到从顶部到底部的最小路径和。每一步可以移动到下面一行的相邻数字上。 ** 注意事项 如果你只用额外空间复杂度O(n)的条件下完成可以获得加分，其中n是数字三角形的总行数。**
最小路径提取算法在很多领域都有广泛应用，医学图像分析，机器人导航等。2008年来自昆士兰科技大学的Dan Mueller开源了基于Fast Marching方式的最小路径提取算法，原理：利用Fast Marching到达函数T的梯度是与波前正交的事实来求解仅有一个的局部最小值，这也是全局最小值。通过从给定种子（路径终点）反向传播到起点来提取最小路径。起点和终点是隐式嵌入在T中的，反向传播可以通过梯度下降和正阶梯度下降来实现。
首先我们分析题目，要找的是三角形最小路径和， 这是个啥意思呢？假设我们有一个三角形：
在PCB印刷电路板设计中，器件之间的连线，要避免线路的阻抗值增大，而且器件之间还有别的器任和别的干扰源，在布线时我们希望受到的干扰尽量小。
题目：一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。 问总共有多少条不同的路径？
今日步步为营，实战dp，采用递推、记忆化、动态规划，三种方法解决两道题目，并深入研究动态规划套路。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
对于简单的 bug 大家轻松定位解决就可以了，但是对于疑难复杂的 bug 这里我们分为 5 个核心流程方法，其中包括：梳理流程、日志分析、最小路径、猜测排除、独立验证。
最短路径，指的是从连接图中的某个顶点出发到达到达另外一个顶点所经过的边的权重和最小的那一条路径。
链接：https://leetcode-cn.com/problems/triangle
在上一篇中，我们通过题目“最长上升子序列”以及"最大子序和"，学习了DP（动态规划）在线性关系中的分析方法。这种分析方法，也在运筹学中被称为“线性动态规划”，具体指的是 “目标函数为特定变量的线性函数，约束是这些变量的线性不等式或等式，目的是求目标函数的最大值或最小值”。这点大家作为了解即可，不需要死记，更不要生搬硬套！
讲解动态规划的资料很多，官方的定义是指把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解。概念中的各阶段之间的关系，其实指的就是状态转移方程。很多人觉得DP难（下文统称动态规划为DP），根本原因是因为DP区别于一些固定形式的算法（比如DFS、二分法、KMP），没有实际的步骤规定第一步第二步来做什么，所以准确的说，DP其实是一种解决问题的思想。
有个小孩正在上楼梯，楼梯有n阶台阶，小孩每次可以上1阶、两阶或者三阶。 计算小孩有多少种上楼梯的方式。结果可能很大，你需要对1000000007取模 样例输入
1、动态规划（英语：Dynamic programming，简称DP）通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 2、动态规划常常适用于有重叠子问题性质的问题，动态规划方法所耗时间往往远少于朴素解法。 3、动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。
当处于 (row,col)位置处时，下一行 可以选择 (row+1,col)位置 / (row+1,col-1)位置 /(row+1,col+1)位置处的元素
这是 LeetCode 上的「120. 三角形最小路径和」，难度为 Medium。
这次来针对具体的一类动态规划问题，矩阵类动态规划问题，来看看针对这一类问题的思路和注意点。
题意是有n个点，m条单向边，然后在边上放机器人，问最少放多少个机器人能遍历到所有的点。
931. 下降路径最小和 题目描述： 给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的下降路径的最小和 。 下降路径可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。
英文版：https://leetcode.com/problems/number-of-islands/description/
哈喽！同学们，今天和大家分享一下，利用Python代码求三角形最小路径和！给定一个三角形，每一步只能移动到下一行中相邻的结点上，求出自顶向下的最小路径和。
算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！
https://tianchi.aliyun.com/oj/338592228998370026/357527484118536805
本文作者labuladong，著有《labuladong的算法小抄》一书。 「魔塔」是一款经典的地牢类游戏，碰怪物要掉血，吃血瓶能加血，你要收集钥匙，一层一层上楼，最后救出美丽的公主。 现在手机上仍然可以玩这个游戏： 嗯，相信这款游戏承包了不少人的童年回忆，记得小时候，一个人拿着游戏机玩，两三个人围在左右指手画脚，这导致玩游戏的人体验极差，而左右的人异常快乐 😂 ▼ 力扣第 174 题是一道类似的题目，我简单描述一下： 输入一个存储着整数的二维数组grid，如果grid[i][j] > 0，说明这个格子
本节，我们讨论关于图的最后一个问题，最短路径问题。在一个有权重的有向图中，我们如何去找到他对应最短的路径内，这是哪怕在我们显示生活中也常见的一个文问题。
相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。
---- 三角形最小路径和题解整理 递归---超时版本 记忆化递归 自上而下的动态规划 自下而上的动态规划 动态规划空间优化 ---- 递归—超时版本 分析： [ [2], [3,4], [6,5,7], [4,1,8,3] ] 相邻结点：与(i, j) 点相邻的结点为 (i + 1, j) 和 (i + 1, j + 1)。 若定义 f(i, j) 为 (i, j) 点到底边的最小路径和，则易知递归求解式为: f(i, j) = min(f(i + 1, j), f(i + 1, j + 1))
我们把要解决的一个大问题转换成若干个规模较小的同类型问题，当我们求解出这些小问题的答案，大问题便不攻自破。这就是动态规划。
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
对象存储
即时通信 IM
实时音视频
