• 【Leetcode】120.三角形最小路径和


    一、题目

    1、题目描述

    给定一个三角形 triangle ,找出自顶向下的最小路径和。

    每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说,如果正位于当前行的下标 i ,那么下一步可以移动到下一行的下标 ii + 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)。
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    示例2:

    输入:triangle = [[-10]]
    输出:-10
    
    • 1
    • 2

    提示:

    • 1 <= triangle.length <= 200
    • triangle[0].length == 1
    • triangle[i].length == triangle[i - 1].length + 1
    • -104 <= triangle[i][j] <= 104

    进阶:

    • 你可以只使用 O(n) 的额外空间(n 为三角形的总行数)来解决这个问题吗?

    2、基础框架

    class Solution {
    public:
        int minimumTotal(vector<vector<int>>& triangle) {
    
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    3、原题链接

    120.三角形最小路径和

    二、解题报告

    1、思路分析

    动态规划 + 空间优化

    动态规划的经典题目,堪称入门题。

    (i,j) 位置看成一个状态,定义 dp[i][j] 表示 从 (i,j) 位置出发得到的最小路径和。在(i,j) 位置有两种决策:向左下走到 (i+1,j) 位置,后续从 (i+1,j) 位置出发得到最小路径和;同理,向右下走到(i+1,j+1) 位置,后续从 (i+1,j+1) 位置出发得到最小路径和。

    所以可以得到转移方程:
    d p [ i ] [ j ] = t r i a n g l e [ i ] [ j ] + m i n ( d p [ i + 1 ] [ j ] , d p [ i + 1 ] [ j + 1 ] ) dp[i][j] = triangle[i][j] + min(dp[i+1][j], dp[i+1][j+1]) dp[i][j]=triangle[i][j]+min(dp[i+1][j],dp[i+1][j+1])

    也就是说,(i,j) 位置的状态依赖于 (i+1,j)(i+1, j+1) 位置的状态,于是逆序枚举 i。见代码详解中的"动态规划"写法。

    (i,j) 位置的状态只依赖于 (i+1,j)(i+1, j+1) 位置的状态,所以用一维数组即可。代码见"动态规划 + 空间优化"写法。

    2、时间复杂度

    O ( N 2 ) O(N^2) O(N2)

    3、代码详解

    • 动态规划
    class Solution {
    public:
        int minimumTotal(vector<vector<int>>& triangle) {
            int n = triangle.size();
    
            int dp[n][n];
            memset(dp, 0, sizeof(dp));
    
            for (int j = 0; j < n; j++) {
                dp[n - 1][j] = triangle[n - 1][j]; //最后一行的状态
            }
    
            for (int i = n - 2; i >= 0; i--) { //逆序枚举
                for (int j = 0; j <= i; j++) {
                    dp[i][j] = triangle[i][j] + min(dp[i + 1][j], dp[i+1][j+1]);
                }
            }
    
            return dp[0][0];
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 动态规划 + 空间优化
    class Solution {
    public:
        int minimumTotal(vector<vector<int>>& triangle) {
            int n = triangle.size();
    
            int dp[n];
            memset(dp, 0, sizeof(dp));
    
            for (int j = 0; j < n; j++) {
                dp[j] = triangle[n - 1][j]; //最后一行的状态
            }
    
            for (int i = n - 2; i >= 0; i--) { //逆序枚举
                for (int j = 0; j <= i; j++) {
                    dp[j] = triangle[i][j] + min(dp[j], dp[j+1]);
                }
            }
    
            return dp[0];
        }
    };
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
  • 相关阅读:
    手写简易操作系统(九)--实现打印函数
    华为机试 - 仿LISP运算
    Python爬虫入门
    CobalStrike(CS)流量分析
    MVC与三层架构
    Linux安装MongoDB(简单详细)
    工具链赋能百家,地平线开启智能驾驶量产的“马太效应”
    npm常见操作
    基于4G工业路由器的信息发布系统物联网应用方案
    如何选择适合的PoE交换机?
  • 原文地址:https://blog.csdn.net/u011386173/article/details/134060925