一起学习交流~

三角形最小路径和-经典dp特殊情况

算法 laomuji 8个月前 (01-22) 314次浏览 已收录 0个评论

目录

题目

给定一个三角形 triangle ,找出自顶向下的最小路径和。
每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说,如果正位于当前行的下标 i ,那么下一步可以移动到下一行的下标 i 或 i + 1 。

示例 1:
输入:triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
输出:11
解释:如下面简图所示:
2
3 4
6 5 7
4 1 8 3
自顶向下的最小路径和为 11(即,2 + 3 + 5 + 1 = 11)。
示例 2:
输入:triangle = [[-10]]
输出:-10
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/triangle
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

题解

[[2],[3,4],[6,5,7],[4,1,8,3]]
画一下

0 1 2 3
2
3 4
6 5 7
4 1 8 3

通过读题目 可以得出 每个长度只能由[i-1][j] 或者 [i-1][j-1] 加上当前长度构成

那么对应的最小路径和为:

0 1 2 3
2
5 6
11 10 13
15 11 18 16
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int maxSize = triangle.size();
        vector<vector<int>>dp = triangle;
        for(int i = 1 ; i<maxSize;i++){
            dp[i][0]+=dp[i-1][0];
            for(int j = 1;j<i;j++){
                dp[i][j]+=min(dp[i-1][j],dp[i-1][j-1]);
            }
            dp[i][i]+=dp[i-1][i-1];
        }
        int minNum=dp[maxSize-1][0];
        for(int i = 1;i<maxSize;i++){
            if(dp[maxSize-1][i]<minNum)minNum = dp[maxSize-1][i];
        }
        return minNum;
    }
};
喜欢 (0)
订阅评论
提醒
guest
0 评论
内联反馈
查看所有评论