三角形最小路径和

我们记dp[i][j]为在第i行第j列处元素的路径和，注意到三角形第i行有i个元素（i从1开始，在数组中下标为[0,n-1]）。我们可以得到如下动态转移方程：

$j$等于0，此时当前元素的路径和只能从上一行的最左边得到：

$$
dp[i][0] = dp[i-1][0] + c[i][0]
$$

$j$等于$i$，此时当前元素的路径和只能从上一行的最右边得到：
$$
dp[i][i] = dp[i-1][i-1] + c[i][i]
$$

其他情况，此时可以从上一行的两个元素处得到：
$$
dp[i][j] = min(dp[i-1][j],dp[i-1][j-1])+c[i][j]
$$

$c[i][j]$表示在$(i,j)$处的元素值。

1	class Solution {
2	public int minimumTotal(List<List<Integer>> triangle) {
3	int n = triangle.size();
4	int[][] dp = new int[n][n];
5	dp[0][0] = triangle.get(0).get(0);
6	for(int i=1; i<n; i++){
7	dp[i][0] = dp[i-1][0] + triangle.get(i).get(0);
8	for(int j=1; j<i; j++){
9	dp[i][j] = Math.min(dp[i-1][j-1], dp[i-1][j]) + triangle.get(i).get(j);
10	}
11	dp[i][i] = dp[i-1][i-1] + triangle.get(i).get(i);
12	}
13	int ans = dp[n-1][0];
14	for(int i=1; i<n; i++){
15	ans = Math.min(ans, dp[n-1][i]);
16	}
17	return ans;
18
19	}
20	}

复杂度分析：

时间复杂度：$O(n^2)$。
空间复杂度：$O(n^2)$。

如果想进一步优化空间复杂度到$O(n)$，需要使用滚动数组，因为观察转移方程$dp[i][j]$的状态只与$dp[i-1][j-1]$和$dp[i-1][j]$有关。如果遍历$j$的时候从$i-1$到$0$遍历，那么只需要一个一维数组即可。如果$j$遍历是正序遍历，那么就会破坏第$i-1$行处$j-1$的值，如果是逆序的话就正好不会破坏。

class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[] dp = new int[n];
        dp[0] = triangle.get(0).get(0);
        for(int i=1; i<n; 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], dp[j-1])+triangle.get(i).get(j);
            }
            dp[0] = dp[0] + triangle.get(i).get(0);
        }
        int ans = dp[0];
        for(int i=1; i<n; i++){
            ans = Math.min(ans, dp[i]);
        }
        return ans;
    }
}