NC225. 三角形最小路径和
描述
示例1
输入:
[[10]]
输出:
10
示例2
输入:
[[2],[3,4],[6,5,7],[4,1,8,3]]
输出:
11
说明:
最小路径是 2 ， 3 ，5 ， 1示例3
输入:
[[1],[-1000,0]]
输出:
-999
C++ 解法, 执行用时: 4ms, 内存消耗: 640KB, 提交时间: 2022-04-22
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param triangle int整型vector<vector<>>
* @return int整型
*/
int minTrace1(vector<vector<int> >& triangle) {
// write code here
int n = triangle.size();
vector<vector<int>> dp(n, vector<int>(n,0));
dp[0][0] = triangle[0][0];
for(int i=1; i<n; i++){
for(int j=0; j<=i; j++){
if(j == 0)
dp[i][j] = dp[i-1][j] + triangle[i][j];
else if(j == i)
dp[i][j] = dp[i-1][j-1] + triangle[i][j];
else
dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j];
}
}
int res = INT_MAX;
for(int i = 0; i<n ; i++)
res = min(res, dp[n-1][i]);
return res;
}
int minTrace(vector<vector<int> >& triangle) {
int n = triangle.size();
vector<int> dp(n+1, 0);
for(int i=n-1; i>=0; i--){
for(int j=0; j<=i; j++){
dp[j] = min(dp[j], dp[j+1]) + triangle[i][j];
}
}
return dp[0];
}
};
C++ 解法, 执行用时: 4ms, 内存消耗: 648KB, 提交时间: 2022-01-27
class Solution {
public:
/*
题意：
给定三角形，每次只能移动到下一行中的相邻结点，求从顶点到底边的最小路径和。
分析：
若定义 f(i, j) 为 (i, j) 点到底边的最小路径和，则易知递归求解式为:
f(i,j)=min(f(i+1,j),f(i+1,j+1))+triangle[i][j]
由此，我们将任一点到底边的最小路径和，转化成了与该点相邻两点到底边的最小路径和中的较小值，
再加上该点本身的值。
方法一：暴力递归（存在大量重复计算，超时）
参考：
https://leetcode-cn.com/problems/triangle/solution/di-gui-ji-yi-hua-dp-bi-xu-miao-dong-by-sweetiee/
*/
int minTrace1(vector<vector<int> >& triangle) {
return dfs(triangle, 0, 0);
}
/*
方法二：记忆化递归（同样超时）
在方法一的基础上，定义了二维数组进行记忆化。
复杂度分析
时间复杂度：O(N^2)，N 为三角形的行数。
空间复杂度：O(N^2)，N 为三角形的行数。
*/
int minTrace2(vector<vector<int> >& triangle) {
vector<vector<int>> memo(triangle.size(), vector<int>(triangle[0].size()));
return dfs(triangle, memo, 0, 0);
}
/*
方法三：动态规划
定义二维 dp 数组，将解法二中「自顶向下的递归」改为「自底向上的递推」。
1、状态定义：
dp[i][j] 表示从点 (i,j) 到底边的最小路径和。
2、状态转移：
dp[i][j]=min(dp[i+1][j],dp[i+1][j+1])+triangle[i][j]
复杂度分析
时间复杂度：O(N^2)，N 为三角形的行数。
空间复杂度：O(N^2)，N 为三角形的行数。
*/
int minTrace3(vector<vector<int> >& triangle) {
int n = triangle.size();
// dp[i][j] 表示从点 (i, j) 到底边的最小路径和。
vector<vector<int> > dp(n + 1, vector<int>(n + 1));
// 从三角形的最后一行开始递推。
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j <= i; j++) {
dp[i][j] = min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j];
}
}
return dp[0][0];
}
/*
动态规划解法优化
空间优化
在上述代码中，我们定义了一个 N 行 N 列 的 dp 数组（N 是三角形的行数）。
但是在实际递推中我们发现，计算 dp[i][j] 时，只用到了下一行的 dp[i+1][j] 和 dp[i+1][j+1]。
因此 dp 数组不需要定义 N 行，只要定义 1 行就阔以啦。
所以我们稍微修改一下上述代码，将 i 所在的维度去掉（如下），就可以将 O(N^2)的空间复杂度优化成 O(N) 啦～
复杂度分析
时间复杂度：O(N^2)，N 为三角形的行数。
空间复杂度：O(N)，N 为三角形的行数。
*/
int minTrace(vector<vector<int> >& triangle) {
int n = triangle.size();
vector<int> dp(n + 1);
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j <= i; j++) {
dp[j] = min(dp[j], dp[j + 1]) + triangle[i][j];
}
}
return dp[0];
}
private:
int dfs(vector<vector<int>> &triangle, int i, int j) {
if (i == triangle.size()) return 0; //行索引i越界，表示找到一条路径
return min(dfs(triangle, i + 1, j), dfs(triangle, i + 1, j + 1)) + triangle[i][j];
}
int dfs(vector<vector<int>> &triangle, vector<vector<int>> &memo, int i, int j) {
if (i == triangle.size()) return 0;
if (memo[i][j] != 0) return memo[i][j];
memo[i][j] = min(dfs(triangle, memo, i + 1, j), dfs(triangle, memo, i + 1, j + 1)) + triangle[i][j];
return memo[i][j];
}
};
C++ 解法, 执行用时: 5ms, 内存消耗: 548KB, 提交时间: 2022-05-29
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param triangle int整型vector<vector<>>
* @return int整型
*/
int minTrace(vector<vector<int> >& triangle) {
// write code here
int row = triangle.size();
int len = triangle[row - 1].size();
vector<int> dp( len, triangle[0][0] );
for (int i = 1; i < row; ++i)
{
for (int j = i; j >= 0; --j)
{
if (j == 0)
dp[j] = dp[j] + triangle[i][j];
else if (j == i)
dp[j] = dp[j - 1] + triangle[i][j];
else
dp[j] = min(dp[j], dp[j - 1]) + triangle[i][j];
}
}
int ret = dp[0];
for (int ele : dp)
ret = ret < ele ? ret : ele;
return ret;
}
};
C++ 解法, 执行用时: 5ms, 内存消耗: 552KB, 提交时间: 2022-08-04
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param triangle int整型vector<vector<>>
* @return int整型
*/
int minTrace(vector<vector<int> >& triangle) {
// write code here
int n = triangle.size();
for(int i = 1; i < n; ++i){
for(int j = 0; j <= i; ++j){
if(j == 0){
triangle[i][j] += triangle[i - 1][j];
}else if(j < i){
triangle[i][j] += min(triangle[i - 1][j - 1], triangle[i - 1][j]);
}else{
triangle[i][j] += triangle[i - 1][j - 1];
}
}
}
return *min_element(triangle[n - 1].begin(), triangle[n - 1].end());
}
};
C++ 解法, 执行用时: 5ms, 内存消耗: 552KB, 提交时间: 2022-01-09
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param triangle int整型vector<vector<>>
* @return int整型
*/
int minTrace(vector<vector<int> >& triangle) {
// write code here
for (int i = triangle.size() - 2; i >= 0; --i) {
for (int k = 0; k < triangle[i].size(); ++k) {
triangle[i][k] += min(triangle[i + 1][k], triangle[i + 1][k +1]);
}
}
return triangle[0][0];
}
};