[leetcode] 120. Triangle

[leetcode] 120. triangle

Description

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.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[i]每一层的第i个节点的值，dp[i] = 当前点值 + min（上一层的左边点值， 上一层的右边点值）。最终算得的结果为dp[0~n]中最小的那个。

代码

class Solution {public: int minimumTotal(vector>& triangle) { vector dp(triangle.size(),0xffffff); dp[0]=0; for(int i=0;i=0;j--){ if(j==0){ dp[j]=dp[j]+triangle[i][j]; }else{ dp[j]=min(dp[j-1],dp[j])+triangle[i][j]; } } } int min_val=INT_MAX; for(int i=0;i

参考文献

​​[编程题]triangle​​​​LeetCode 120. Triangle (三角形最小路径和）详解​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。