代码如下：
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
// 创建表格
int[][] dp = new int[triangle.size()][triangle.size()];
dp[0][0] = triangle.get(0).get(0);
// 动态规划的方程式
for (int i = 1; i < dp.length; i++) {
for (int j = 0; j <= i; j++) {
int curr = triangle.get(i).get(j);
if (j == 0) {
dp[i][j] = dp[i-1][j] + curr;
} else if (j == i) {
dp[i][j] = dp[i-1][j-1] + curr;
} else {
dp[i][j] = Math.min(dp[i-1][j-1], dp[i-1][j]) + curr;
}
}
}
int res = dp[triangle.size()-1][0];
for (int j = 1; j < triangle.size(); j++) {
res = Math.min(res, dp[triangle.size()-1][j]);
}
return res;
}
}
下面来分析这个问题的时间复杂度以及空间复杂度，一般来说空间复杂度是就是 DP 表格的大小。
在这道问题中是 O(n^2)，而对于时间复杂度来说，就是整个 dp 的遍历次数，而在这个问题中我们只进行了一次遍历，也即一个矩阵的遍历，所以是O(n^2)。
而如果想要优化到 O(n)，我们需要怎么做呢？
实际上这个就涉及到了一种状态压缩的方法，也即压缩这个状态表。
那么怎么去压缩呢？
这个问题比较简单，因为dp[i][j]仅仅与上一层的状态有关，所以说与前两层的是没有任何关系的，因此我们不必存储这些无关的状态。
实际上最简单的状态压缩就是保留好前两个状态即可，例如在计算第四行的时候，保留第三行以及第二行的状态表，然后交替的进行更新就可以啦。
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
// 只保留最近 2 行
int[][] dp = new int[2][triangle.size()];
dp[0][0] = triangle.get(0).get(0);
for (int i = 1; i < triangle.size(); i++) {
int row = i % 2;
int prevRow = (i-1) % 2;
for (int j = 0; j <= i; j++) {
if (j == 0) {
dp[row][j] = dp[prevRow][j] + triangle.get(i).get(j);
} else if (j == i) {
dp[row][j] = dp[prevRow][j-1] + triangle.get(i).get(j);
} else {
dp[row][j] = Math.min(dp[prevRow][j-1], dp[prevRow][j]) + triangle.get(i).get(j);
}
}
}
int res = dp[(triangle.size() - 1) % 2][0];
for (int j = 1; j < triangle.size(); j++) {
res = Math.min(res, dp[(triangle.size() - 1) % 2][j]);
}
return res;
}
}
这个的空间复杂度是 O(2n)，能不能压缩成严格意义上的O(n)呢？
那么再往后是否还能够进行状态的压缩呢？
答案是可以的，我们可以再想一种方程然后达到最优的空间复杂度的目标。
当我们在计算位置 [i][j] 时，f[j+1] 到 f[i] 已经是第 i 行的值，而 f[0] 到 f[j] 仍然是第 i-1 行的值。
此时我们直接通过 f[j] = min(f[j−1], f[j]) + c[i][j]来计算，但是这个时候我们需要j 是倒着遍历的，因为这样才不会影响之前记录下的状态。
如果从 1 开始，那么计算 2 的时候就会用到新的 1 的数值而不是上一层 1 的数值。
代码如下：
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int[] dp = new int[triangle.size()];
dp[0] = triangle.get(0).get(0);
for (int i = 1; i < triangle.size(); i++) {
dp[i] = dp[i-1] + triangle.get(i).get(i);
for (int j = i-1; j > 0; j--) {
dp[j] = Math.min(dp[j-1], dp[j]) + triangle.get(i).get(j);
}
dp[0] += triangle.get(i).get(0);
}
int res = dp[0];
for (int j = 1; j < triangle.size(); j++) {
res = Math.min(res, dp[j]);
}
return res;
}
}
方法 2
方法 1 有点绕，但如果自下向上来理解，就会变得很简单，这个方法也叫 bottom-up，方法 1 则是 top-down。
从结果出发，这个问题是一个发散三角树的问题，从最后一行出发，然后每一行每一行的进行递推，那么第一行就是最终的结果了。
举个最简单的例子：
1
1 2
如果从最底下往上出发，实际上找最小值方法的规律很容易找到，那就是在第二行[1， 2]里面选择一个就可以了，因为他们两个都要走到根节点。
也就是在下一行的两个数里面取个小的就行了，那么结果就是第一行的数值。
我们先用二维的转移矩阵来解释这个问题，用这种方法也不需要考虑方法 1 里面的边界条件了：
dp[i][j] = min(dp[i+1][j], dp[i+1][j+1]) + c[i][j]
状态转换图如下所示：
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int[][] dp = new int[triangle.size()][triangle.size()];
// 创建 DP 空间
for (int i = 0; i < triangle.size(); i++) {
dp[triangle.size() - 1][i] = triangle.get(triangle.size() - 1).get(i);
}
for (int i = triangle.size() - 2; i >= 0; i--) {
for (int j = 0; j < triangle.get(i).size(); j++) {
dp[i][j] = Math.min(dp[i+1][j], dp[i+1][j+1]) + triangle.get(i).get(j);
}
}
return dp[0][0];
}
}
那么在进行状态压缩的时候，我们该怎么去做呢？
实际上就是只用一个状态表来表示所有的。
因为只是和上一个状态相关，所以说可以表示成如下的形式：
dp[j] = min(dp[j], dp[j + 1]) + triangle[i][j]，
我们只用 j 来代表当前的状态，然后最终输出dp[0]即可。
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int[] dp = new int[triangle.size()];
// 创建 DP 空间
for (int i = 0; i < triangle.size(); i++) {
dp[i] = triangle.get(triangle.size() - 1).get(i);
}
for (int i = triangle.size() - 2; i >= 0; i--) {
for (int j = 0; j <= i; j++) {
dp[j] = Math.min(dp[j], dp[j+1]) + triangle.get(i).get(j);
}
}
return dp[0];
}
}
深圳网站建设www.sz886.com
