Triangle(动态规划)

题目描述

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below. For example, given the following triangle

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

The minimum path sum from top to bottom is11(i.e., 2 + 3 + 5 + 1 = 11). Note:
Bonus point if you are able to do this using only
O(n) extra space, where n is the total number of
rows in the triangle.

题意:

  给定一个数字三角形,找到从顶部到底部的最小路径和。每一步可以移动到下面一行的相邻数字上。

解题思路:

  • 矩阵型DP问题
  • 自顶而下或者自底而上
  • 采用一个向量dp,复制。三角形最后一行,作为用来更新的一位数组。然后逐个遍历这个dp数组,对于每个数字,和它之后的元素比较选择较小的再加上上面一行相邻位置的元素做为新的元素,然后一层一层的向上扫描,整个过程和冒泡排序的原理差不多,最后最小的元素都冒到前面,第一个元素即为所求。

代码实现:

class Solution {
public:
    int minimumTotal(vector<vector<int> > &triangle) {
        int n=triangle.size();
        vector<int>dp(triangle.back());
        for(int i=n-2;i>=0;i--){
            for(int j=0;j<=i;j++){
                dp[j]=min(dp[j+1],dp[j])+triangle[i][j];
            }
        }
        return dp[0];
    }
};
时间: 11-12

Triangle(动态规划)的相关文章

LeetcodeOJ: Triangle 动态规划

Total Accepted: 31557 Total Submissions: 116793 Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below. [ [2], [3,4], [6,5,7], [4,1,8,3] ] The minimum path sum from top to bottom is

poj 1163 The Triangle (动态规划)

The Triangle Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 37778   Accepted: 22685 Description 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 (Figure 1) Figure 1 shows a number triangle. Write a program that calculates the highest sum of numbers passed

nyoj 18 The Triangle 动态规划

和nyoj613(免费馅饼)一样的原理  从下 网上依次遍历 存贮最大值 #include <stdio.h> #include <algorithm> using namespace std; int main() { int n,num[105][105]={0}; scanf("%d",&n); for(int i=1;i<=n;i++) for(int j=1;j<=i;j++) scanf("%d",&n

[LeetCode][JavaScript]Triangle

Triangle Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below. For example, given the following triangle [ [2], [3,4], [6,5,7], [4,1,8,3] ] The minimum path sum from top to bottom

leetCode(47):Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below. For example, given the following triangle [ [2], [3,4], [6,5,7], [4,1,8,3] ] The minimum path sum from top to bottom is 11 (i

动态规划第五讲——leetcode上的题目动态规划汇总(上)

本节,我们将对leetcode上有关DP问题的题目做一个汇总和分析. 1.题目来源 Interleaving String 动态规划 二叉树 Unique Binary Search Trees 动态规划 二叉树 Word Break 动态规划 N/A Word Break II 动态规划 N/A Palindrome Partitioning 动态规划 N/A Palindrome Partitioning II 动态规划 N/A Triangle 动态规划 N/A Distinct Subs

九章算法系列(#3 Dynamic Programming)-课堂笔记

前言 时隔这么久才发了这篇早在三周前就应该发出来的课堂笔记,由于懒癌犯了,加上各种原因,实在是应该反思.好多课堂上老师说的重要的东西可能细节上有一些急记不住了,但是幸好做了一些笔记,还能够让自己回想起来.动态规划算是我的一道大坎了,本科的时候就基本没有学过,研一的时候老师上课也是吃力的跟上了老师的步伐,其实那个时候老师总结的还是挺好的:把动态规划的题目都分成了一维动规.二维遍历.二维不遍历等一系列的问题.这次听了老师的课程,觉得还是需要更加集中的去把各种题进行一个分类吧,然后有针对的去准备,虽然

leetcode解题目录

参考文献:http://blog.csdn.net/lanxu_yy/article/details/17848219 不过本文准备用超链接的方式连接到相应解答页面,不断更新中 题目 算法 数据结构 注意事项 Clone Graph BFS 哈希表 Word Ladder II BFS 哈希表 Surrounded Regions BFS 矩阵 Word Ladder BFS N/A Binary Tree Level Order Traversal BFS|前序遍历 队列 Binary Tre

LeetCode -- Triangle 路径求最小和( 动态规划问题)

人们常说"细节决定成败". 编码工作中,同样需要关注细节. 本文将给出3个小实例来说明编码中关注细节的重要性,同时给出作者对如何注意编码细节的一点见解(说的不对,请指正). 例1 这个问题如此地显而易见,竟然没有被发现. List<int> numList = new List<int>(); numList.Add(3); numList.Add(1); numList.Add(4); numList.Add(2); numList.Add(5); numLi

leetcode_120题——Triangle (动态规划)

Triangle Total Accepted: 39052 Total Submissions: 143341My Submissions Question Solution Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below. For example, given the following tri