一、動態(tài)規(guī)劃簡介
動態(tài)規(guī)劃 , 英文名稱 Dynamic Programming , 簡稱 DP , 不是具體的某種算法 , 是一種算法思想 ;
具體的算法都有具體的步驟 , 如 : 二分法 , 其 有固定的解決步驟 , 先取一個中心點 , 判斷解在左邊還是右邊 , 然后在一邊再取一個中心點 , 再進行判定 , 該算法有具體的步驟 ;
動態(tài)規(guī)劃 , 沒有具體的步驟 , 只有一個核心思想 ;
動態(tài)規(guī)劃 的 核心思想 是 由大化小 , 大規(guī)模問題 使用 小規(guī)模問題 計算結果 解決 , 類似于 分治算法 ;
動態(tài)規(guī)劃 與 貪心算法 區(qū)別 :
- 動態(tài)規(guī)劃 會 為了長遠利益 損害當前利益 ; 動態(tài)規(guī)劃 不僅僅 考慮下一步的利益 , 還 對 后面十幾步甚至幾十步進行了大量計算 , 得到了最佳結果 ;
- 貪心算法 只注重 當前利益最大化 ; 貪心算法 只考慮下一步的最佳利益 ;
動態(tài)規(guī)劃 實現(xiàn)方法 :
- 遞歸 : 如 記憶化搜索 的實現(xiàn) ;
- for 循環(huán) : 使用 多重 for 循環(huán) 實現(xiàn) ;
二、自底向上的動態(tài)規(guī)劃示例
從 下圖的 數(shù)字三角形 中 從上到下 找到一條 最短路徑 ;
1、原理分析
自底向上 的動態(tài)規(guī)劃思想 : 下面的 n 的最佳路徑 指的是 以 n 為起點 到達 最底層的 的最短路徑 ;
頂部的 1 的最佳路徑 依賴于 2 和 3 中的 最佳路徑 , 選擇最佳的路徑即可 ;
- 2 的最佳路徑 依賴于 4 和 -5 中的最佳路徑 ,
- 4 的最佳路徑 依賴于 7 和 8 中的最佳路徑 ,
- -5 的最佳路徑 依賴于 8 和 9 中的最佳路徑 ,
- 3 的最佳路徑 依賴于 -5 和 6 中的最佳路徑 ,
- -5 的最佳路徑 依賴于 8 和 9 中的最佳路徑 ,
- 6 的最佳路徑 依賴于 9 和 10 中的最佳路徑 ,
最后一排中 ( 第四排 ) :
- 7 走到最底層的 最小路徑 是其本身 7
- 8 走到最底層的 最小路徑 是其本身 8
- 9 走到最底層的 最小路徑 是其本身 9
- 10 走到最底層的 最小路徑 是其本身 10
倒數(shù)第二排 ( 第三排 ) :
- 4 的 最短路徑 從 7 和 8 之間取最短的最短路徑 , 是 7 , 對應最短路徑 7 , 最短路徑為 4 + 7 = 11
- -5 的最短路徑 從 8 和 9 之間取最短的最短路徑 , 是 8 , 對應最短路徑 8 , 最短路徑為 -5 + 8 = 3
- 6 的 最短路徑 從 9 和 10 之間取最短的最短路徑 , 是 9 , 對應最短路徑 9 , 最短路徑為 6 + 9 = 15
倒數(shù)第三排 ( 第二排 ) :
- 2 的 最短路徑 從 4 和 -5 之間取最短的最短路徑 , 是 -5 , 對應最短路徑 3 , 最短路徑為 2 + 3 = 5
- 3 的最短路徑 從 -5 和 6 之間取最短的最短路徑 , 是 -5 , 對應最短路徑 3 , 最短路徑為 3 + 3 = 6
倒數(shù)第四排 ( 第一排 ) :
- 1 的 最短路徑 從 2 和 3 之間取最短的最短路徑 , 是 2 , 對應最短路徑 5 , 最短路徑為 1 + 5 = 6
通過分析 , 可以得出 從 1 開始的最短路徑為 1 -> 2 -> -5 -> 8 , 最短路徑為 6 ;
2、算法設計
將下圖的數(shù)據(jù) , 存放到 二維數(shù)組 triangle 中 , 作為 數(shù)據(jù)源 使用 ;
該 triangle 二維數(shù)組 ,
- 第 0 行有 1 個數(shù)字 ,
- 第 1 行有 2 個數(shù)字 ,
… , - 第 n-1 行有 n 個數(shù)字 ;
該二維數(shù)組的長度 , 就是 數(shù)字三角形 中的行數(shù) ;
狀態(tài)記錄 : 創(chuàng)建 二維數(shù)組 dp , dp[i][j] 表示從 第 i 行 第 j 列的元素出發(fā) , 數(shù)組的元素值就是走到最底層的最短路徑 ;
dp 二維數(shù)組 的作用就是用于 記錄狀態(tài)值 , 如 :
- dp[0][0] 表示從第 0 行第 0 列 的 1 出發(fā) , 走到最底層的最短路徑 , 其值為 6 ;
- dp[3][2] 表示從第 3 行第 2 列 的 -5 出發(fā) , 走到最底層的最短路徑 , 其值為 3 ;
dp[0] 只有一個有效元素 , dp[1] 有兩個有效元素 , dp[2] 有三個有效元素 , dp[4] 有四個有效元素 ;
初始化數(shù)據(jù) : 假設 該 三角形有 n 行數(shù)據(jù) ;
那么 , 第 n - 1 行 , 也就是最后一行 , 該 n - 1 行有 n 個數(shù)字 , i 取值 0 ~ n - 1 , 則 dp[n-1][i] 的值就是 其本身 triangle[n-1][i]
數(shù)字三角形 最后一行 數(shù)字 , 即 n -1 行 數(shù)字 , 作為 初始化數(shù)據(jù) ; 然后開始從 n - 2 行開始計算 ;
運算方程 : 設置具體的算法如何進行計算 , 從 n - 2 行開始計算 本行數(shù)據(jù)的 最短路徑 ;
n - 2 行 的 第 i 個數(shù)字 的 最短路徑 , 依賴于 n - 1 行 的 第 i 個數(shù)字 和 第 i + 1 個數(shù)字 的 最短路徑 , 取較小的最短路徑 ;
最終結果 : 使用上述 運算方程 從 第 n - 2 行 進行遍歷 , 最終計算出 第 0 行 第 0 列 數(shù)字元素的最短路徑 , 存儲在二維數(shù)組 dp[0][0] 元素上 ;
上述算法中 二維數(shù)組 dp 中 , 每個元素 , 第 dp[i][j] 就是一個 子問題 , 表示 數(shù)字三角形中 第 i 行 第 j 列 元素的 最短路徑 , 通過這些子問題的解決 , 最終得到一個 大規(guī)模問題的 解決方案 ;
3、代碼示例
代碼示例 :
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Solution {
/**
* 三角形最短路徑
* @param triangle 三角形數(shù)據(jù)
* @return
*/
public int minimumTotal(List<List<Integer>> triangle) {
int n = triangle.size();
// 動態(tài)規(guī)劃狀態(tài) :
// dp[i][j] 表示從 第 i 行 第 j 列的元素出發(fā) ,
// 數(shù)組的元素值就是走到最底層的最短路徑 ;
int[][] dp = new int[n][n];
// 動態(tài)規(guī)劃初始化 :
// 第 n - 1 行 , 也就是最后一行 , 該 n - 1 行有 n 個數(shù)字 , i 取值 0 ~ n - 1 ,
// 則 dp[n-1][i] 的值就是 其本身 triangle[n-1][i]
// 數(shù)字三角形 最后一行 數(shù)字 , 即 n -1 行 數(shù)字 , 作為 初始化數(shù)據(jù) ;
// 然后開始從 n - 2 行開始計算 ;
for (int i = 1; i < n; i++) {
dp[n - 1][i] = triangle.get(n - 1).get(i);
}
// 動態(tài)規(guī)劃方程 :
// n - 2 行 的 第 i 個數(shù)字 的 最短路徑 ,
// 依賴于 n - 1 行 的 第 i 個數(shù)字 和 第 i + 1 個數(shù)字 的 最短路徑 ,
// 取較小的最短路徑 ;
for (int i = n - 2; i > -1; i--) {
for (int j = 0; j < i + 1; j++) {
dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) // 先取一個最短路徑最小值
+ triangle.get(i).get(j); // 再加上改點計算出一個新的最短路徑
}
}
// 動態(tài)規(guī)劃結果 :
// 使用上述 運算方程 從 第 n - 2 行 進行遍歷 ,
// 最終計算出 第 0 行 第 0 列 數(shù)字元素的最短路徑 ,
// 存儲在二維數(shù)組 dp[0][0] 元素上 ;
return dp[0][0];
}
public static void main(String[] args) {
List<List<Integer>> triangle = new ArrayList<List<Integer>>(){
{
add(new ArrayList<Integer>(Arrays.asList(1)));
add(new ArrayList<Integer>(Arrays.asList(2, 3)));
add(new ArrayList<Integer>(Arrays.asList(4, -5, 6)));
add(new ArrayList<Integer>(Arrays.asList(7, 8, 9, 10)));
}
};
int minTotal = new Solution().minimumTotal(triangle);
System.out.println("三角形最短路徑為 " + minTotal);
}
}
執(zhí)行結果 :
三角形最短路徑為 6
三、自頂向下的動態(tài)規(guī)劃示例
從 下圖的 數(shù)字三角形 中 從上到下 找到一條 最短路徑 ;
每個點 都有 從起點開始 走到該點 的 最短路徑 ; 如
- 4 這個點 , 從 起點 1 開始走 , 肯定走 1 -> 2 -> 4 路線 是最短路徑 , 為 7 ;
- -5 這個點 , 從 起點 1 開始走 , 肯定走 1 -> 2 -> -5 路線 是最短路徑 , 為 -2 ;
1、算法設計
狀態(tài)記錄 : 創(chuàng)建 二維數(shù)組 dp , dp[i][j] 表示從 起點 走到 第 i 行 第 j 列的元素的最短路徑 , 數(shù)組的元素值就是走到最底層的最短路徑 ;
dp 二維數(shù)組 的作用就是用于 記錄狀態(tài)值 , 如 :
- dp[0][0] 表示 從起點 第 0 行第 0 列 的 1 出發(fā) , 走到當前點 第 0 行第 0 列 的 1 的最短路徑 , 其值為 1 ;
- dp[3][2] 表示 從起點 第 0 行第 0 列 的 1 出發(fā) , 走到當前點 第 3 行第 2 列 的 -5 的最短路徑 , 其值為 -2 ;
dp[0] 只有一個有效元素 , dp[1] 有兩個有效元素 , dp[2] 有三個有效元素 , dp[4] 有四個有效元素 ;
初始化數(shù)據(jù) : 沒有辦法套入 動態(tài)規(guī)劃方程 中的點 進行初始化操作 ;
在套用下面的 運算方程時 , 會發(fā)現(xiàn) , 最左側的一排數(shù)字 , 沒有左上角的元素 , 也就是 第 i 行 第 j 列 的數(shù)字 其左上角的數(shù)字是 第 i - 1 行 第 j - 1 列 , 如果 j = 0 , 那么左上角 j - 1 肯定為負數(shù) ; 因此 最左側一列 和 最右側一列 是無法在 運算方程中直接計算的 ;
此處初始化 頂點 的最短路徑 , 和 最左側一列 和 最右側一列 數(shù)字 的最短路徑 ;
運算方程 : 設置具體的算法如何進行計算 , 從 n - 2 行開始計算 本行數(shù)據(jù)的 最短路徑 ;
第 i 行 第 j 列 的數(shù)字 , 從頂點走到該點的最短路徑 , 依賴于 左上角 第 i - 1 行 第 j - 1 列 的 數(shù)字 的最短路徑 , 和 右上角 的 第 i - 1 行 第 j 列 的 數(shù)字 的 最短路徑 , 找出 上面 二者 最短路徑較小 的最短路徑 作為結果 ;
最終結果 : 在進行最后一層 計算時 , 會得到 第 n - 1 層 , 也就是最后一層 , 所有元素的最短路徑 , 選擇 最小的 最短路徑 , 就是本次的最短路徑 ;
上述算法中 二維數(shù)組 dp 中 , 每個元素 , 第 dp[i][j] 就是一個 子問題 , 表示 數(shù)字三角形中 從起點開始 到 第 i 行 第 j 列 元素的 最短路徑 , 通過這些子問題的解決 , 最終得到一個 大規(guī)模問題的 解決方案 ;
2、代碼示例
代碼示例 :
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Solution {
/**
* 三角形最短路徑
* @param triangle 三角形數(shù)據(jù)
* @return
*/
public int minimumTotal(List<List<Integer>> triangle) {
int n = triangle.size();
// 動態(tài)規(guī)劃狀態(tài) :
// dp[i][j] 表示從 起點 走到 第 i 行 第 j 列的元素的最短路徑 ,
// 數(shù)組的元素值就是走到最底層的最短路徑 ;
int[][] dp = new int[n][n];
// 動態(tài)規(guī)劃初始化 : 沒有辦法套入 動態(tài)規(guī)劃方程 中的點 進行初始化操作
// 起始點的最短路徑是其本身
dp[0][0] = triangle.get(0).get(0);
// 遍歷 1 ~ n 行
for (int i = 1; i < n; i++) {
// 每行第 0 個元素的 最短路徑 , 該元素沒有左上角的點
dp[i][0] = dp[i - 1][0] + triangle.get(i).get(0);
// 每行第 n - 1 個元素的 最短路徑 , 該元素沒有右上角的點
dp[i][i] = dp[i - 1][i - 1] + triangle.get(i).get(i);
}
// 動態(tài)規(guī)劃方程 :
// 第 i 行 第 j 列 的數(shù)字 , 走到該點的最短路徑 ,
// 依賴于 左上角 第 i - 1 行 第 j - 1 列 的 數(shù)字 的最短路徑 ,
// 和 正上方的 第 i - 1 行 第 j 列 的 數(shù)字 的 最短路徑 ,
// 找出 上面 二者 最短路徑較小 的最短路徑 作為結果 ;
// 此處從 i = 2 開始 , 是因為 第一排的兩個數(shù)字的最短路徑已經(jīng)初始化過了 , 在初始化中已經(jīng)進行了初始化
for (int i = 2; i < n; i++) {
// j 的取值只能是 1 ~ i - 1 , 將每一行的 第 0 個 和 第 i 個 元素剔除出去
for (int j = 1; j < i; j++) {
dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle.get(i).get(j);
}
}
// 動態(tài)規(guī)劃結果 :
// 在進行最后一層 計算時 , 會得到 第 n - 1 層 , 也就是最后一層 , 所有元素的最短路徑 ,
// 選擇 最小的 最短路徑 , 就是本次的最短路徑 ;
int minTotal = dp[n - 1][0];
for (int i = 1; i < n; ++i) {
minTotal = Math.min(minTotal, dp[n - 1][i]);
}
return minTotal;
}
public static void main(String[] args) {
List<List<Integer>> triangle = new ArrayList<List<Integer>>(){
{
add(new ArrayList<Integer>(Arrays.asList(1)));
add(new ArrayList<Integer>(Arrays.asList(2, 3)));
add(new ArrayList<Integer>(Arrays.asList(4, -5, 6)));
add(new ArrayList<Integer>(Arrays.asList(7, 8, 9, 10)));
}
};
int minTotal = new Solution().minimumTotal(triangle);
System.out.println("三角形最短路徑為 " + minTotal);
}
}
執(zhí)行結果 :文章來源：http://www.zghlxwxcb.cn/news/detail-795540.html
三角形最短路徑為 6
文章來源地址http://www.zghlxwxcb.cn/news/detail-795540.html
到了這里，關于【算法】動態(tài)規(guī)劃 ① ( 動態(tài)規(guī)劃簡介 | 自底向上的動態(tài)規(guī)劃示例 | 自頂向下的動態(tài)規(guī)劃示例 )的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！
