LeetCode120，求教
来源：9-3 发现重叠子问题 Integer Break
qq_山上山_0
2020-05-21
啵啵老司，感觉这个120，看起来简单，怎么做起来有点难啊
总感觉哪里没想明白；又好像用回溯法才对，因为要全部加了才知道那条路径是最小的
1、如果测试用例是[
[2],
[3,4],
[6,5,7],
[400,100,8,3]
] 该怎么办？而且看了递归做的，感觉状态转移方程还是没悟出来
/// 120. 三角形最小路径和 （C#）
public int MinimumTotal(IList<IList<int>> triangle)
{
int n = triangle.Count;
int a = triangle[0][0];
for (int i = 0; i < n-1; i++)
{
for (int j = i; j < i+2; j++)
{
a = a + Math.Min(triangle[i+1][j], triangle[i+1][j + 1]);
}
}
return a;
}
写回答
1回答
-
liuyubobobo
2020-05-21
dp[i][j] 的意思是，走到 (i, j) 位置的最小 sum。
走到 (i, j) 位置的最小 sum，是和走到 (i - 1, j - 1) 位置的最小 sum 和 (i - 1, j) 位置的最小 sum 相关的。即两者取其一，再加上当前位置的值。
状态转移方程：
dp[i][j] = triangle[i][j] + min(dp[i - 1][j - 1], dp[i - 1][j])
我的参考代码：https://github.com/liuyubobobo/Play-Leetcode/blob/master/0120-Triangle/cpp-0120/main.cpp
继续加油！：）
00
相似问题
leetcode37. 数独求教
回答 1
LeetCode130求教
回答 1
leetCode131求教
回答 1
LeetCode 63 求教
回答 1
波波老师求教word search2
回答 2