[leetcode]动态规划之Triangle

缺乏、安全感 2021-09-28 14:46 444阅读 0赞

### 动态规划之Triangle ###

*  题目
 *  思考
 *  答案

# 题目 #

[leetcode入口][leetcode]

# 思考 #

刚开始想这道题，想着的是建立一维的表格。  
但是到某一层的距离，不能用到前面层的距离表示。

查了网上答案，  
看了在求每一层的最小距离的时候，需要求得到该层每一个格子的最短距离，最后求该层最小的值  
因此每层都要叠加。

# 答案 #

class Solution { 
    public:
        int minimumTotal(vector<vector<int>>& triangle) { 
            int level=triangle.size();
            for(int i=1;i<level;i++){ 
                int this_level=triangle[i].size();
                for(int j=0;j<this_level;j++){ 
                    if(j==0){ 
                        triangle[i][j]+=triangle[i-1][j];
                    }
                    else if(j==this_level-1){ 
                        triangle[i][j]+=triangle[i-1][j-1];
                    }
                    else{ 
                        triangle[i][j]+=min(triangle[i-1][j-1],triangle[i-1][j]);
                    }
                }
            }
            
            int min=0x7ffffff;
            for(int j=0;j<triangle[level-1].size();j++){ 
                if(min>triangle[level-1][j]){ 
                    min=triangle[level-1][j];
                }
            }
            
            return min;
            
        }
    };

[leetcode]: https://leetcode.com/problems/triangle/

发表评论取消回复

表情：

评论列表（有 0 条评论，444人围观）

还没有评论，来说两句吧...

相关阅读

相关动态规划之Triangle(三角形) Java实现

问题给定一个三角形的数字阵列，选择一条自顶向下的路径，使得沿途的所有数字之和最小。（每一步只能移动到相邻的格子中） ![在这里插入图片描述][20201224195

深藏阁楼爱情的钟/ 2022年12月30日 08:29/ 0 赞/ 120 阅读

相关 LeetCode高级算法之动态规划

[152. Maximum Product Subarray][] 这题与最大子序列和不同的地方在于, 乘积的状态转移不能用dp\[i-1\]\num\[i\]来获得, 因为

深藏阁楼爱情的钟/ 2022年12月28日 04:04/ 0 赞/ 112 阅读

相关 leetcode动态规划

1. 爬楼梯假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？动态规划模板题，思考方法，1个台

布满荆棘的人生/ 2022年09月05日 04:07/ 0 赞/ 147 阅读

相关【LeetCode】120. Triangle 基于C++和Java的分析及解法，动态规划

120. Triangle Total Accepted: 69567 Total Submissions: 229977 Difficulty: Medium Gi

缺乏、安全感/ 2022年07月24日 06:13/ 0 赞/ 122 阅读

相关 [leetcode]动态规划之PerfectSquare

动态规划之PerfectSquare 题目思考代码数学方法动态规划题目 [leetcode题目入口][lee

客官°小女子只卖身不卖艺/ 2021年09月29日 02:10/ 0 赞/ 278 阅读

相关 [leetcode]动态规划之Ugly Number

动态规划之Ugly Number 题目思考代码题目 [leetcode入口][leetcode] 思考这是一道结合了数学的dp题

秒速五厘米/ 2021年09月29日 01:52/ 0 赞/ 279 阅读

相关 [leetcode]动态规划之CountingBits

动态规划之CountingBits 题目思考代码题目 [leetcode入口][leetcode] 思考这道题让我思考了dp数组

心已赠人/ 2021年09月29日 01:40/ 0 赞/ 272 阅读

相关 [leetcode]动态规划之Maximal Square

动态规划之Maximal Square 题目思考代码题目 [leetcode入口][leetcode] 思考之前认为dp表格的含

心已赠人/ 2021年09月29日 01:40/ 0 赞/ 301 阅读

相关 [leetcode]动态规划之wordbreak

动态规划之wordbreak 题目知识点思考代码题目 [leetcode入口][leetcode] 知识点 unorder

短命女/ 2021年09月28日 14:48/ 0 赞/ 303 阅读

相关 [leetcode]动态规划之Triangle

动态规划之Triangle 题目思考答案题目 [leetcode入口][leetcode] 思考刚开始想这道题，想着的是建立一维

缺乏、安全感/ 2021年09月28日 14:46/ 0 赞/ 445 阅读