专栏首页算法修养LeetCode 120 Triangle

LeetCode 120 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

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.

c++

class Solution {
public:
    int dp[1005][1005];
    int minimumTotal(vector<vector<int>>& triangle) {
        
        int len = triangle.size();
        dp[0][0] = triangle[0][0];
        for(int i=1;i<len;i++)
        {
            int l = triangle[i].size();
            for(int j=0;j<l;j++)
            {
                if(j==0)
                    dp[i][j] = triangle[i][j]+dp[i-1][j];
                else if(j==l-1)
                    dp[i][j] = triangle[i][j]+dp[i-1][j-1];
                else
                    dp[i][j] = min(triangle[i][j]+dp[i-1][j],triangle[i][j]+dp[i-1][j-1]);
            }
        }
        int ans = 9999999;
        for(int i=0;i<triangle[len-1].size();i++)
        {
            ans = min(ans,dp[len-1][i]);
        }
        return ans;
        
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 118 Pascal's Triangle

    Given a non-negative integer numRows, generate the first numRows of Pascal's tri...

    ShenduCC
  • LeetCode 119 Pascal's Triangle II

    Given a non-negative index k where k ≤ 33, return the kth index row of the Pasca...

    ShenduCC
  • LeetCode 354 Russian Doll Envelopes (动态规划)

    一道好题目,把最长递增子序列扩展到二维,但是这道题和最长递增子序列是有区别的,它不要求是序列,只是在数组中找到一组最长的组合,不要求顺序在初始中相同。

    ShenduCC
  • Dynamic Programming - 120. Triangle

    Given a triangle, find the minimum path sum from top to bottom. Each step you ma...

    用户5705150
  • 【leetcode刷题】T160-三角形最小路径和

    https://leetcode-cn.com/problems/triangle/

    木又AI帮
  • 《剑指offer》第27天:三角形最小路径和

    首先我们分析题目,要找的是三角形最小路径和, 这是个啥意思呢?假设我们有一个三角形:

    程序员小浩
  • 漫画:动态规划系列 第四讲

    在上一篇中,我们通过题目“最长上升子序列”以及"最大子序和",学习了DP(动态规划)在线性关系中的分析方法。这种分析方法,也在运筹学中被称为“线性动态规划”,具...

    程序员小浩
  • LeetCode 684. 冗余连接(并查集)

    输入一个图,该图由一个有着N个节点 (节点值不重复1, 2, …, N) 的树及一条附加的边构成。附加的边的两个顶点包含在1到N中间,这条附加的边不属于树中已存...

    Michael阿明
  • 图论-网络流-最大流--POJ1273Drainage Ditches(Dinic)

    Every time it rains on Farmer John's fields, a pond forms over Bessie's favorite...

    风骨散人Chiam
  • Android实现可点击的幸运大转盘

    这是效果图,实现目标:十二星座的图片可点击切换选中效果,根据选择不同的星座,实现不同的 方法。之前网上的都是带有指针的,或者可点击改变效果,但是并不知道选择的到...

    砸漏

扫码关注云+社区

领取腾讯云代金券