数字三角形最小路径和—动态规划

思路:自底向上求解,从倒数第二行开始,本行节点到最后一行的最小路径和等于该节点的数据加上下面左右两个数据中最小的一个。不使用额外空间,直接将最小路径和存储到原有的数组中。1 int minimumTotal(vector<vector<int>> &triangle) {
2         // write your code here
3         for (int i = triangle.size() - 2; i >= 0; i--) {
4             for (int j = 0; j < triangle[i].size(); j++) {
5                 triangle[i][j] = min(triangle[i+1][j], triangle[i+1][j+1]) + triangle[i][j];
6             }
7         }
8         return triangle[0][0];
9     }
时间: 09-22

数字三角形最小路径和—动态规划的相关文章

#动态规划 LeetCode 120 三角形最小路径和

给定一个三角形,找出自顶向下的最小路径和.每一步只能移动到下一行中相邻的结点上. 例如,给定三角形: [ [2], [3,4], [6,5,7], [4,1,8,3] ] 自顶向下的最小路径和为 11(即,2 + 3 + 5 + 1 = 11). 说明: 如果你可以只使用 O(n) 的额外空间(n 为三角形的总行数)来解决这个问题,那么你的算法会很加分. 思路: 接着上一题的状态转移继续说 动态规划问题,重中之重就是找到状态转移方程,而状态转移方程很重要的一点就是明确函数的意义所在,以及记录结果

LeetCode 120——三角形最小路径和

1. 题目 2. 解答 详细解答方案可参考北京大学 MOOC 程序设计与算法(二)算法基础之动态规划部分. 从三角形倒数第二行开始,某一位置只能从左下方或者右下方移动而来,因此,我们只需要求出这两者的较小值然后再加上当前元素,即可得出从某一位置到最下边的最小路径和.以此类推,我们就可以求出最上边元素的最小路径和.过程如下所示: 2 3 4 6 5 7 4 1 8 3 第三行到最下边的最小元素和 7 6 10 3 min(4, 1) + 6 min(1, 8) + 5 min(8, 3) + 7

数字三角形(蓝桥杯 动态规划)

问题描述 (图3.1-1)示出了一个数字三角形. 请编一个程序计算从顶至底的某处的一条路 径,使该路径所经过的数字的总和最大. ●每一步可沿左斜线向下或右斜线向下走: ●1<三角形行数≤100: ●三角形中的数字为整数0,1,-99: . (图3.1-1) 输入格式 文件中首先读到的是三角形的行数. 接下来描述整个三角形 输出格式 最大总和(整数) 样例输入 573 88 1 02 7 4 44 5 2 6 5 样例输出 30 从最下面往上找,由局部最优解找整体最优解. #include<st

LeetCode—Minimum Path Sum 二维数组最小路径,动态规划

感觉这是一系列的动态规划的算法,正好也将动态规划的算法进行一个总结: 算法一: 带权重的最小路径的问题 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. 首先每一个路径的上一个路径都是来自于其上方和左方 现将最上面的路径进行求和,最左边的路径进行求和

120. 三角形最小路径和

给定一个三角形,找出自顶向下的最小路径和.每一步只能移动到下一行中相邻的结点上. 例如,给定三角形: [ [2], [3,4], [6,5,7], [4,1,8,3] ] 自顶向下的最小路径和为 11(即,2 + 3 + 5 + 1 = 11). 说明: 如果你可以只使用 O(n) 的额外空间(n 为三角形的总行数)来解决这个问题,那么你的算法会很加分. 逆向思维,从底向顶部找,状态转移方程 minimus[i][j]=data[i][j]+min(minimums[i+1][j]+minimu

算法52-----矩阵最小路径【动态规划】

一.题目:矩阵最小路径 给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小. 说明:每次只能向下或者向右移动一步. 示例: 输入: [   [1,3,1], [1,5,1], [4,2,1] ] 输出: 7 解释: 因为路径 1→3→1→1→1 的总和最小. 思路1:时间O(M*N),空间O(M*N) 新建一个矩阵dp(大小也是M*N),该矩阵是从上往下,从左往右记录每一步的结果的,当前的结果可以根据该矩阵上面和左边最小的值来获得,即: dp[

三角形最小路径和

给定一个三角形,找出自顶向下的最小路径和.每一步只能移动到下一行中相邻的结点上. 例如,给定三角形: [ [2], [3,4], [6,5,7], [4,1,8,3] ] 自顶向下的最小路径和为 11(即,2 + 3 + 5 + 1 = 11). 说明: 如果你可以只使用 O(n) 的额外空间(n 为三角形的总行数)来解决这个问题,那么你的算法会很加分. 1.自顶向下带备忘录的方法 class Solution { private int[][] cache; public int minimu

最小路径(动态规划)

1.最小路径和(矩形) 给定一个只含非负整数的m*n网格,找到一条从左上角到右下角的可以使数字和最小的路径. 注:你在同一时间只能向下或者向右移动一步 样例1:1 3 1 1 5 1 4 2 1 输出:7 样例2: 1 3 5 9 8 1 3 4 5 0 6 1 8 8 4 0 输出:12 import java.util.Scanner; public class Main { public static void main(String[] args) { // TODO Auto-gene

最小路径和—动态规划

思路:定义一个网格大小的二维数组,先为第一行和第一列赋值.然后后面的值等于网格当前值加上二维数组上面和右面的最小的值. 1 int minPathSum(vector<vector<int>> &grid) { 2 // write your code here 3 int row = grid.size(); 4 int col = grid[0].size(); 5 int ** sum = new int*[row]; 6 for (int i = 0; i <