您当前的位置: 首页 >  动态规划

星许辰

暂无认证

  • 0浏览

    0关注

    466博文

    0收益

  • 0浏览

    0点赞

    0打赏

    0留言

私信
关注
热门博文

LeetCode_动态规划_中等_120.三角形最小路径和

星许辰 发布时间:2022-07-23 14:25:50 ,浏览量:0

目录
  • 1.题目
  • 2.思路
  • 3.代码实现(Java)

1.题目

给定一个三角形 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

提示: 1 11 10 13 0 11 10 13 0 4 1 8 3 4 1 8 3 4 1 8 3 => 14 11 18 16 => 11 即为自顶向下的最小路径和

③ 在求解过程中注意要考虑边界问题,并且由于该方法使用了 n * n 的二维数组 matrix,故其空间复杂度为 O(n2)。在空间复杂度上,本题还可进一步优化,具体细节可参考本题官方题解。

相关题目: LeetCode_动态规划_中等_64.最小路径和

3.代码实现(Java)
//思路1————动态规划
class Solution {
    public int minimumTotal(List triangle) {
        int res = Integer.MAX_VALUE;
        int n = triangle.size();
        if (n == 1) {
            return triangle.get(0).get(0);
        }
        //将三角形 triangle 中的结点存储到 matrix 中(形状变为等腰直角三角形,只占 matrix 左下部分空间)
        int[][] matrix = new int[n][n];
        for (int i = 0; i             
关注
打赏
1665627467
查看更多评论
0.0834s