動態規劃
- 2021 年 6 月 28 日
- 筆記
- 數據結構與演算法分析
概念：
之前的問題與當前的問題有關聯，利用之前問題的答案遞推當前問題的答案。
給定一個三角形，找出自頂向下的最小路徑和。每一步只能移動到下一行中相鄰的結點上。
題目：
給定三角形：
[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]
自頂向下的最小路徑和為 11（即，2 + 3 + 5 + 1 = 11，嘗試使用 O(n) 的額外空間（n 為三角形的總行數）來解決這個問題。）
解題思路：
-
問題拆解：
這裡的總問題是求出最小的路徑和，路徑是這裡的分析重點，路徑是由一個個元素組成的，
[i][j]位置的元素，經過這個元素的路徑肯定也會經過[i - 1][j]或者[i - 1][j - 1]，因此經過一個元素的路徑和可以通過這個元素上面的一個或者兩個元素的路徑和得到。 -
狀態定義
狀態的定義一般會和問題需要求解的答案聯繫在一起，這裡其實有兩種方式，一種是考慮路徑從上到下，另外一種是考慮路徑從下到上，因為元素的值是不變的，所以路徑的方向不同也不會影響最後求得的路徑和，如果是從上到下，你會發現，在考慮下面元素的時候，起始元素的路徑只會從
[i - 1][j]獲得，每行當中的最後一個元素的路徑只會從[i - 1][j - 1]獲得，中間二者都可。 -
遞推方程
「狀態定義」 中我們已經定義好了狀態，遞推方程就出來了
dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + triangle[i][j]
1 class Solution { 2 public int minimumTotal(List<List<Integer>> triangle) { 3 int n = triangle.size(); 4 int[][] f = new int[n][n]; 5 f[0][0] = triangle.get(0).get(0); 6 for (int i = 1; i < n; ++i) { 7 f[i][0] = f[i - 1][0] + triangle.get(i).get(0);//當元素位於最左端的時候 8 for (int j = 1; j < i; ++j) {//元素位於中間 9 f[i][j] = Math.min(f[i - 1][j - 1], f[i - 1][j]) + triangle.get(i).get(j); 10 } 11 f[i][i] = f[i - 1][i - 1] + triangle.get(i).get(i);//元素位於最右 12 } 13 int minTotal = f[n - 1][0]; 14 for (int i = 1; i < n; ++i) { 15 minTotal = Math.min(minTotal, f[n - 1][i]); 16 } 17 return minTotal; 18 } 19 }
