题目链接：点我做题
我们把这个三角形每个点的下标视为矩阵中的点，那么可以定义
f
(
i
,
j
)
f(i,j)
f(i,j)为自
(
0
,
0
)
(0,0)
(0,0)点到
(
i
,
j
)
(i,j)
(i,j)点的最短路径，状态转移方程就是考虑到上一层的每个点的最短路径已经计算过的情况下，这一层的值怎么得来。
由于下一层比上一层多出一个元素，所以下一层有两个点是特殊的，一个是下标为0的点，它只能由上一层下标为0的点到达，另一个是下标为当前层数i的点，它只能由上一层的下标为
i
−
1
i-1
i−1的点到达；其他点(下标为j)均可以由上一层的下标为
j
−
1
j-1
j−1的点和下标为
j
j
j的点到达，因此状态转移方程就得到了：
1.
j
=
=
0
,
f
(
i
,
j
)
=
f
(
i
−
1
,
0
)
+
t
r
i
a
n
g
l
e
[
i
]
[
j
]
最
左
边
上
只
能
从
上
一
层
的
最
左
边
上
来
2.
j
=
=
i
,
f
(
i
,
j
)
=
f
(
i
−
1
,
j
−
1
)
+
t
r
i
a
n
g
l
e
[
i
]
[
j
]
最
右
边
上
只
能
从
上
一
层
的
最
右
边
上
来
3.
其
他
f
(
i
,
j
)
=
m
i
n
(
f
(
i
−
1
,
j
−
1
)
,
f
(
i
−
1
,
j
)
)
+
t
r
i
a
n
g
l
e
[
i
]
[
j
]
1.j == 0, f(i,j) = f(i - 1, 0) + triangle[i][j] 最左边上 只能从上一层的最左边上来\ 2.j == i, f(i,j) = f(i - 1, j - 1) + triangle[i][j] 最右边上 只能从上一层的最右边上来\ 3.其他 f(i,j) = min(f(i - 1, j - 1), f(i - 1, j)) + triangle[i][j]
1.j==0,f(i,j)=f(i−1,0)+triangle[i][j]最左边上只能从上一层的最左边上来2.j==i,f(i,j)=f(i−1,j−1)+triangle[i][j]最右边上只能从上一层的最右边上来3.其他f(i,j)=min(f(i−1,j−1),f(i−1,j))+triangle[i][j]
由此，可以写出代码：
下面的代码是修改了原数组中的数据，如果不允许修改原数组中的数据则新开一个二维数组
d
p
dp
dp即可，行数和列数均为
l
e
v
e
l
level
level.
class Solution {
public:
int minimumTotal(vector>& triangle)
{
int level = triangle.size();
for (int i = 1; i < level; ++i)
{
for (int j = 0; j <= i; ++j)
{
if (j == 0)
{
triangle[i][j] = triangle[i - 1][0] + triangle[i][j];
}
else if (j == i)
{
triangle[i][j] = triangle[i - 1][j - 1] + triangle[i][j];
}
else
{
triangle[i][j] = triangle[i][j] +
min(triangle[i - 1][j - 1], triangle[i - 1][j]);
}
}
}
int ret = triangle[level - 1][0];
for (auto e : triangle[level - 1])
{
if (ret > e)
{
ret = e;
}
}
return ret;
}
};
观察到本行状态仅和上一行状态有关，因此可以利用滚动数组优化空间复杂度:
class Solution {
public:
int minimumTotal(vector>& triangle)
{
int level = triangle.size();
vector dp(level);
dp[0] = triangle[0][0];
for (int i = 1; i < level; ++i)
{
for (int j = i; j >= 0; --j)
{
if (j == 0)
{
dp[0] = dp[0] + triangle[i][j];
}
else if (j == i)
{
dp[j] = dp[j - 1] + triangle[i][j];
}
else
{
dp[j] = min(dp[j - 1], dp[j]) + triangle[i][j];
}
}
}
int ret = dp[0];
for (auto e : dp)
{
ret = min(ret, e);
}
return ret;
}
};
时间复杂度:
O
(
N
)
O(N)
O(N),N为三角形中点的个数
空间复杂度:
O
(
l
e
v
e
l
)
O(level)
O(level)，level为三角形层数
本题更自然的一个状态定义是定义
F
(
i
.
j
)
F(i.j)
F(i.j)为
(
i
,
j
)
(i,j)
(i,j)到最底层的最短距离，那么我们要的答案就是
F
(
0
,
0
)
F(0,0)
F(0,0),并且由于我们这样定义了，我们只能先从底下的行往上算，初始状态就是
t
r
i
a
n
g
l
e
triangle
triangle数组最后一行的值，然后在已知前一行到底层的最短距离的情况下，对于点
(
i
,
j
)
(i,j)
(i,j)，显然要么它走到下一层的
(
i
+
1
,
j
)
(i+1,j)
(i+1,j)从而到达最底层，要么走到下一层的
(
i
+
1
,
j
+
1
)
(i+1,j+1)
(i+1,j+1)从而到达最底层。
由于每上一层点会比上一层少一个，因此这种动态规划的状态转移方程不需要考虑边界情况，状态转移方程为：
f
(
i
,
j
)
=
m
i
n
(
f
(
i
+
1
,
j
)
,
f
(
i
+
1
,
j
+
1
)
)
+
t
r
i
a
n
g
l
e
(
i
,
j
)
f(i,j)=min(f(i+1,j),f(i+1,j+1))+triangle(i,j)
f(i,j)=min(f(i+1,j),f(i+1,j+1))+triangle(i,j)
代码如下：
class Solution {
public:
int minimumTotal(vector>& triangle)
{
int level = triangle.size();
vector> F(level, vector(level));
for (int j = 0; j < level; ++j)
{
F[level - 1][j] = triangle[level - 1][j];
}
for (int i = level - 2; i >= 0; --i)
{
for (int j = 0; j <= i; ++j)
{
F[i][j] = min(F[i + 1][j], F[i + 1][j + 1]) + triangle[i][j];
}
}
return F[0][0];
}
};
同理，本方法也可以优化空间复杂度：
class Solution {
public:
int minimumTotal(vector>& triangle)
{
int level = triangle.size();
vector dp(level);
for (int j = 0; j < level; ++j)
{
dp[j] = triangle[level - 1][j];
}
for (int i = level - 2; i >= 0; --i)
{
for (int j = 0; j <= i; ++j)
{
dp[j] = min(dp[j], dp[j + 1]) + triangle[i][j];
}
}
return dp[0];
}
};
时间复杂度:
O
(
N
)
O(N)
O(N)
空间复杂度:
O
(
l
e
v
e
l
)
O(level)
O(level)
