当前位置：首页 > article >正文

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

article 2025/1/21 12:01:51

题目

LCR 100. 三角形最小路径和

中等

思路和解题方法

首先定义了一个类 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;
    }
}

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

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

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

查看全文

http://www.kler.cn/a/146002.html