自学内容网 自学内容网

力扣:120. 三角形最小路径和

力扣:120. 三角形最小路径和

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

每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说,如果正位于当前行的下标 i ,那么下一步可以移动到下一行的下标 i 或 i + 1 。
在这里插入图片描述

方法1:动态规划

定义一个与原来数组有相同位数的二元数组,其中的成员,对应原二维数组的每个成员的最小路径
对于一行中的各个成员的最小路径的计算,而计算主要涉及三个部分,第一部分为左边靠边位置,第二部分为右边靠边的位置,其余为中间位置。
第一部分计算为:本行靠左成员的值 + 到达上一个(上面一行靠左)的最小路径
第二部分计算为:本行靠右成员的值 + 到达上一个(上面一行靠右)的最小路径
第三部分计算为:min(到达上面一个,上面靠左一个)路径最小值 + 本行成员的值
在这里插入图片描述

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

class Solution{
public:
int mininumtotal(vector<vector<int>>& triangle) {
int n = triangle.size();
vector<vector<int>> f(n, vector<int>(n));
f[0][0] = triangle[0][0];
for (int i = 1; i < n; ++i) {
f[i][0] = f[i - 1][0] + triangle[i][0];
for (int j = 1; j < i; ++j) {
f[i][j] = min(f[i - 1][j - 1], f[i - 1][j]) + triangle[i][j];
}
f[i][i] = f[i - 1][i - 1] + triangle[i][i];
}
return *std::min_element(f[n - 1].begin(), f[n - 1].end());
}
};

int main() {
Solution solution;
vector<vector<int>> triangle = {
{2},
{3,4},
{6,5,7},
{4,1,8,3}
};
int result = solution.mininumtotal(triangle);
cout << "mininum path sum is " << result << endl;
return 0;
}

在这里插入图片描述

方法二:动态规划+空间优化

使用二维数组

后一行中的成员路径值,只与本行以及前一行有关,可以定义两行n列的数组,将其值进行拷贝,直至最后只有最后两行中的成员路径数值
在这里插入图片描述

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        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 *std::min_element(f[(n - 1) % 2].begin(), f[(n - 1) % 2].end());
    }
};

int main()
{
Solution solution;
vector<vector<int>> triangle = {
{2},
{3,4},
{6,5,7},
{4,1,8,3}
};
int result = solution.minimumTotal(triangle);
cout << "mininum path sum  == " << result << endl;
return 0;
}

在这里插入图片描述

使用一维数组

从上向下,从右向左计算,计算的结果,存储在一维数组中,覆盖上一行的结果
比如二行开始,
其首先计算的为f[1] = f[0] + triangle[1][1] ,存储为f[1]
再计算f[0] = f[0] + triangle[1][0],存储为f[0]

计算第三行
其首先计算的为f[2] =f[1] + triangle[2][2] ,存储为f[2]
再计算的为f[1] = min(f[0],f[1]) + triangle[2][1] ,存储为f[1]
再计算f[0] = f[0] + triangle[2][0],存储为f[0]
以此类推,计算到n行时,更新完成

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;
class Solution {
public:
int mininumTotal(vector<vector<int>>& triangle) {
int n = triangle.size();
vector<int> f(n);
f[0] = triangle[0][0];
for (int i = 1; i < n; ++i) {
f[i] = f[i - 1] + triangle[i][i];
for (int j = i - 1; j > 0; --j) {
f[j] = min(f[j], f[j - 1]) + triangle[i][j];
}
f[0] = f[0] + triangle[i][0];
}
return *min_element(f.begin(), f.end());
}
};



int main()
{
Solution solution;
vector<vector<int>> triangle = {
{2},
{3,4},
{6,5,7},
{4,1,8,3}
};
int result = solution.mininumTotal(triangle);
cout << "mininum path sum  == " << result << endl;
return 0;
}

在这里插入图片描述


原文地址:https://blog.csdn.net/yuanshenzhilu/article/details/137877984

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!