力扣LCR100题三角形最小路径和C++动态规划附Java代码

题目

LCR 100. 三角形最小路径和

中等

相关标签

数组   动态规划

给定一个三角形 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 <= triangle.length <= 200triangle[0].length == 1triangle[i].length == triangle[i - 1].length + 1-104 <= triangle[i][j] <= 104

进阶：

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

注意：本题与主站 120 题相同： 力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

思路和解题方法

首先定义了一个类 Solution，其中包含了一个公有成员函数 minimumTotal，该函数接收一个二维 vector triangle 作为参数，并返回一个整数作为最小路径和的结果。

在 minimumTotal 函数中，首先获取了三角形的行数 n，然后定义了一个二维 vector dp 用于存储中间状态的计算结果。其中 dp[i][j] 表示从三角形顶部到位置 (i, j) 的最小路径和。

接着对 dp 数组进行初始化，将顶部的值赋为 triangle[0][0]，表示三角形顶部的路径和就是顶部元素的值。

然后使用动态规划的思想，从第二行开始遍历每一行，依次计算每个位置的最小路径和。具体地，对于每一行的第一个元素和最后一个元素，它们只能由上一行对应位置的元素到达，因此可以直接计算出它们的最小路径和；对于每一行的其他位置，它们可以由上一行相邻的两个位置中的较小值到达，因此需要取上一行相邻位置的最小路径和中的较小值，并加上当前位置的值，得到当前位置的最小路径和。

最后，在计算完所有位置的最小路径和后，对最后一行的路径和进行排序，取最小值作为结果返回。

复杂度         时间复杂度:

                O(n*n)

        时间复杂度为 O(n^2)，其中 n 为三角形的行数。这是因为在动态规划的过程中，我们需要计算每个位置的最小路径和，而每个位置需要 O(1) 的时间来进行计算，总共有大约 n^2 个位置需要计算。

        空间复杂度

                O(n*n)

        空间复杂度也为 O(n^2)，因为我们使用了一个二维数组 dp 来存储中间状态的计算结果，其大小为 n*n，所以空间复杂度也与 n 的平方成正比。

c++ 代码 class Solution { public: int minimumTotal(vector<vector<int>>& triangle) { // 获取三角形的行数 int n = triangle.size(); // 创建一个二维数组dp来保存每个位置的最小路径和 vector<vector<int>> dp(n,vector<int>(n)); // 初始化dp数组的第一个元素为三角形顶部的元素值 dp[0][0] = triangle[0][0]; // 从第二行开始遍历三角形的每一行 for(int i= 1;i<n;++i) { // 每一行的第一个元素只能由上一行的第一个元素得到 dp[i][0] = dp[i-1][0] + triangle[i][0]; // 每一行的最后一个元素只能由上一行的最后一个元素得到 dp[i][i] = dp[i-1][i-1] + triangle[i][i]; // 遍历每一行的中间元素 for(int j = 1;j<i;++j) { // 中间元素的最小路径和为上一行相邻两个元素中较小的那个加上当前元素的值 dp[i][j] = min(dp[i-1][j-1] , dp[i-1][j]) + triangle[i][j]; } } // 返回dp数组最后一行中的最小值，即为整个三角形的最小路径和 sort(dp[n-1].begin(),dp[n-1].end()); return dp[n-1][0]; } }; C++优化代码 class Solution { public: int minimumTotal(vector<vector<int>>& triangle) { // 获取三角形的行数 int n = triangle.size(); // 定义一个二维数组 f 用于存储中间状态的计算结果，使用滚动数组进行优化 vector<vector<int>> f(2, vector<int>(n)); // 初始化三角形顶部的最小路径和 f[0][0] = triangle[0][0]; // 从第二行开始遍历每一行 for (int i = 1; i < n; ++i) { int curr = i % 2; int prev = 1 - curr; // 计算每一行的第一个元素的最小路径和 f[curr][0] = f[prev][0] + triangle[i][0]; // 计算每一行的其他位置的最小路径和 for (int j = 1; j < i; ++j) { f[curr][j] = min(f[prev][j - 1], f[prev][j]) + triangle[i][j]; } // 计算每一行的最后一个元素的最小路径和 f[curr][i] = f[prev][i - 1] + triangle[i][i]; } // 返回最后一行中的最小路径和 return *min_element(f[(n - 1) % 2].begin(), f[(n - 1) % 2].end()); } };

Java代码 class Solution { public int minimumTotal(List<List<Integer>> triangle) { // 获取三角形的行数 int n = triangle.size(); // 定义二维数组 f 用于存储中间状态的计算结果 int[][] f = new int[n][n]; // 初始化三角形顶部的最小路径和 f[0][0] = triangle.get(0).get(0); // 从第二行开始遍历每一行 for (int i = 1; i < n; ++i) { // 计算每一行的第一个元素的最小路径和 f[i][0] = f[i - 1][0] + triangle.get(i).get(0); // 计算每一行的其他位置的最小路径和 for (int j = 1; j < i; ++j) { f[i][j] = Math.min(f[i - 1][j - 1], f[i - 1][j]) + triangle.get(i).get(j); } // 计算每一行的最后一个元素的最小路径和 f[i][i] = f[i - 1][i - 1] + triangle.get(i).get(i); } // 对最后一行的路径和进行排序，取最小值作为结果返回 int minTotal = f[n - 1][0]; for (int i = 1; i < n; ++i) { minTotal = Math.min(minTotal, f[n - 1][i]); } return minTotal; } }

Java优化代码 class Solution { public int minimumTotal(List<List<Integer>> triangle) { // 获取三角形的行数 int n = triangle.size(); // 定义一个二维数组 f 用于存储中间状态的计算结果，使用滚动数组进行优化 int[][] f = new int[2][n]; // 初始化三角形顶部的最小路径和 f[0][0] = triangle.get(0).get(0); // 从第二行开始遍历每一行 for (int i = 1; i < n; ++i) { int curr = i % 2; int prev = 1 - curr; // 计算每一行的第一个元素的最小路径和 f[curr][0] = f[prev][0] + triangle.get(i).get(0); // 计算每一行的其他位置的最小路径和 for (int j = 1; j < i; ++j) { f[curr][j] = Math.min(f[prev][j - 1], f[prev][j]) + triangle.get(i).get(j); } // 计算每一行的最后一个元素的最小路径和 f[curr][i] = f[prev][i - 1] + triangle.get(i).get(i); } // 对最后一行的路径和进行排序，取最小值作为结果返回 int minTotal = f[(n - 1) % 2][0]; for (int i = 1; i < n; ++i) { minTotal = Math.min(minTotal, f[(n - 1) % 2][i]); } return minTotal; } }

觉得有用的话可以点点赞，支持一下。

如果愿意的话关注一下。会对你有更多的帮助。

每天都会不定时更新哦  >人<  。