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