题目链接
题目描述
实现代码
初次代码采用dfs的思想实现,每层元素只有两个选择:取或者不取,而从当前位置往下又有两个选择,取左边和去右边,因此,针对这两个选择进行dfs递归实现;
代码如下,结果超时:
package ccnu.agile.jdk8;
import ccnu.agile.utils.JSONUtils;
import java.util.ArrayList;
import java.util.List;
/**
* @Description:
* @Author: JreamY
* @Date: 2022/2/25
**/
public class Demo {
int result = Integer.MAX_VALUE;
public static void main(String[] args) {
List<List<Integer>> triangle = new ArrayList<>();
List<Integer> list1= new ArrayList<>();
list1.add(2);
List<Integer> list2 = new ArrayList<>();
list2.add(3);
list2.add(4);
List<Integer> list3 = new ArrayList<>();
list3.add(6);
list3.add(5);
list3.add(7);
List<Integer> list4 = new ArrayList<>();
list4.add(4);
list4.add(1);
list4.add(8);
list4.add(3);
triangle.add(list1);
triangle.add(list2);
triangle.add(list3);
triangle.add(list4);
System.out.println(new Demo().minimumTotal(triangle));
}
public int minimumTotal(List<List<Integer>> triangle) {
dfs(triangle, 1, 0, triangle.get(0).get(0), triangle.size());
return result;
}
public void dfs(List<List<Integer>> triangle, int layer, int curIdx, int res, int size) {
if(layer == size+1) {
return;
}
if(layer == size) {
result = Math.min(result, res);
return;
}
dfs(triangle, layer+1, curIdx, res+triangle.get(layer).get(curIdx), size);
dfs(triangle, layer+1, curIdx+1, res+triangle.get(layer).get(curIdx+1), size);
}
}
参考官方动态规划思想:记数组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]) + c[i][j]
同时考虑边界条件:
- dp[0][0] = c[0][0];
- 对于j=0的数据,dp[i][j] = dp[i-1][j] + c[i][j];
- 对于i == j的数据,dp[i][j] = dp[i-1][j-1] + c[i][j];
代码如下:
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
// dfs(triangle, 1, 0, triangle.get(0).get(0), triangle.size());
// return result;
int len = triangle.size();
int[][] dp = new int[len][len]; // 顶部到第i行j列位置的最短路径和
// 初始化边界条件
dp[0][0] = triangle.get(0).get(0);
for (int i = 1; i < len; i++) {
for (int j = 0; j < i+1; j++) {
if(j == 0) {
dp[i][j] = dp[i-1][j] + triangle.get(i).get(j);
continue;
}
if(i == j) {
dp[i][j] = dp[i-1][j-1] + triangle.get(i).get(j);
continue;
}
dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - 1]) + triangle.get(i).get(j);
}
}
int min = dp[len-1][0];
for (int i = 1; i < len; i++) {
if (dp[len-1][i] < min) {
min = dp[len-1][i];
}
}
return min;
}
}