題目
在一個(gè)由數(shù)字組成的三角形中，第1行有1個(gè)數(shù)字，第2行有2個(gè)數(shù)字，以此類推，第n行有n個(gè)數(shù)字。例如，下圖是一個(gè)包含4行數(shù)字的三角形。如果每步只能前往下一行中相鄰的數(shù)字，請(qǐng)計(jì)算從三角形頂部到底部的路徑經(jīng)過的數(shù)字之和的最小值。從三角形頂部到底部的路徑數(shù)字之和的最小值為11，對(duì)應(yīng)的路徑經(jīng)過的數(shù)字用陰影表示。
說明：從三角形頂部到底部的路徑數(shù)字之和的最小值為11，對(duì)應(yīng)的路徑經(jīng)過的數(shù)字用陰影表示文章來源：http://www.zghlxwxcb.cn/news/detail-792485.html
分析
可以移動(dòng)三角形每行的位置使它們左端對(duì)齊
可以用f（i，j）表示從三角形的頂部出發(fā)到達(dá)行號(hào)和列號(hào)分別為i和j（i≥j）的位置時(shí)路徑數(shù)字之和的最小值，同時(shí)用T[i][j]表示三角形行號(hào)和列號(hào)分別為i和j的數(shù)字。如果三角形中包含n行數(shù)字，那么f（n-1，j）的最小值就是整個(gè)問題的最優(yōu)解。文章來源地址http://www.zghlxwxcb.cn/news/detail-792485.html
解
public class Test {
public static void main(String[] args) {
List<Integer> list1 = Arrays.asList(2);
List<Integer> list2 = Arrays.asList(3, 4);
List<Integer> list3 = Arrays.asList(6, 5, 7);
List<Integer> list4 = Arrays.asList(4, 1, 8, 3);
List<List<Integer>> triangle = Arrays.asList(list1, list2, list3, list4);
int result = minimumTotal(triangle);
System.out.println(result);
}
public static int minimumTotal(List<List<Integer>> triangle) {
int size = triangle.size();
int[][] dp = new int[size][size];
for (int i = 0; i < size; i++) {
for (int j = 0; j <= i; j++) {
dp[i][j] = triangle.get(i).get(j);
if (i > 0 && j == 0) {// 最左邊
dp[i][j] += dp[i - 1][j];
}
else if (i > 0 && i == j) {// 最右邊
dp[i][j] += dp[i - 1][j - 1];
}
else if (i > 0) {
dp[i][j] += Math.min(dp[i - 1][j], dp[i - 1][j - 1]);
}
}
}
int min = Integer.MAX_VALUE;
for (int num : dp[size - 1]) {// 答案在最底層，選出一個(gè)最小的
min = Math.min(min, num);
}
return min;
}
}
到了這里，關(guān)于面試算法100：三角形中最小路徑之和的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
