做线上兼职哪个网站比较靠谱/怎么建自己的网站?

链接：https://leetcode-cn.com/problems/triangle
给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

例如，给定三角形：

[[2],[3,4],[6,5,7],[4,1,8,3]
]

自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

说明：

如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分

解题：
针对这问题，利用动态规划解题，首先介绍两种方法（图片来源网络）：

方法一：

自顶向下：

每次只需要关注上一行与其相邻的最小值，比如：

[[2],[3,4],[6,5,7],[4,1,8,3]
]

当前值 dp[i][j]，只需关注 Min(dp[i-1][j], dp[i-1][j-1]) 即可

状态定义：dp[i][j]表示包含第i行第j列元素的最小路径和
状态分析
初始化：

dp[0][0]=triangle[0][0]

常规：
triangle[i][j]一定会经过triangle[i-1][j]或者triangle[i-1][j-1],
故：

dp[i][j]  = min( dp[i-1][j], dp[i-1][j-1]) + triangle[i][j]

注意需要做边角处理：

triangle[i][0]没有左上角 只能从triangle[i-1][0]经过
triangle[i][row[0].length]没有上面 只能从triangle[i-1][j-1]经过

转换方程：
dp[i][j]=min(dp[i-1][j],dp[i-1][j-1])+triangle[i][j]
代码：

 public static int minimumTotal1(List<List<Integer>> triangle) {if(triangle == null || triangle.size() == 0){return 0;}int N = triangle.size();int M = triangle.get(N-1).size();int[][] dp = new int[N][M];dp[0][0] = triangle.get(0).get(0);for (int i = 1; i < N; i++) {for (int j = 0; j <= i; j++) {if(j == 0){   // 处理dp[i][0]dp[i][j] = dp[i-1][j] + triangle.get(i).get(j);}else if(j == i){  // 处理dp[i][Max]dp[i][j] = dp[i-1][j-1] + triangle.get(i).get(j);}else{dp[i][j] = Math.min(dp[i-1][j], dp[i-1][j-1]) + triangle.get(i).get(j);}}}int minVal = Integer.MAX_VALUE;for(int i=0; i<M; i++){if(minVal > dp[N-1][i]){minVal = dp[N-1][i];}}return minVal;}

空间优化
观察自顶向下的代码会发现，对第i行的最小路径和的推导，只需要第i-1行的dp[i - 1][j]和dp[i - 1][j - 1]元素即可。可以使用两个变量暂存。
一维的dp数组只存储第i行的最小路径和。

 public int minimumTotal(List<List<Integer>> triangle) {// 特判if (triangle == null || triangle.size() == 0) {return 0;}// dp最大长度==triangle底边长度// 题意：只使用 O(n) 的额外空间（n 为三角形的总行数）int[] dp = new int[triangle.size()];dp[0] = triangle.get(0).get(0);// prev暂存dp[i-1][j-1],cur暂存dp[i-1][j]int prev = 0, cur;for (int i = 1; i < triangle.size(); i++) {//对每一行的元素进行推导List<Integer> rows = triangle.get(i);for (int j = 0; j <= i; j++) {cur = dp[j];if (j == 0) {// 最左端特殊处理dp[j] = cur + rows.get(j);} else if (j == i) {// 最右端特殊处理dp[j] = prev + rows.get(j);} else {dp[j] = Math.min(cur, prev) + rows.get(j);}prev = cur;}}int res = Integer.MAX_VALUE;// dp最后一行记录了最小路径for (int i = 0; i < triangle.size(); i++) {res = Math.min(res, dp[i]);}return res;}

时间复杂度：O(n^2) （n 为三角形的总行数）
空间复杂度：O(n) （n 为三角形的总行数）

方法二：

自底向上：

状态定义：dp[i][j]表示包含第i行第j列元素的最小路径和
状态分析：当前值 dp[i][j] 每次取 dp[i+1][j] 与 dp[i+1][j+1] 之间的最小值，再加在当前值。即可得转移方程：

dp[i][j] = min( dp[i+1][j] , dp[i+1][j+1]) + triangle.get(i).get(j);

代码：

public static int minimumTotal2(List<List<Integer>> triangle) {if(triangle == null || triangle.size() == 0){return 0;}int N = triangle.size();int M = triangle.get(N-1).size();int[][] dp = new int[N+1][M+1];for (int i = N-1; 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];}

空间优化

    public int minimumTotal(List<List<Integer>> triangle) {// 特判if (triangle == null || triangle.size() == 0) {return 0;}// dp中记录了求第i行时，第i+1的最小路径和int[] dp = new int[triangle.size() + 1];for (int i = triangle.size() - 1; i >= 0; i--) {List<Integer> rows = triangle.get(i);for (int j = 0; j < rows.size(); j++) {dp[j] = Math.min(dp[j], dp[j + 1]) + rows.get(j);}}return dp[0];}