動態規劃:
動態規劃（Dynamic Programming，DP）是運籌學的一個分支，是求解決策程序最優化的程序，適用動態規劃的問題必須滿足：
- 最優化原理（最優子結構）：每個階段的最優狀態可以從之前某個階段的某個或某些狀態直接得到；
- 無后效性：不需要管之前這個狀態是如何得到的，
- 子問題重疊：動態規劃演算法的關鍵在于解決冗余，這是動態規劃演算法的根本目的，動態規劃實質上是一種以空間換時間的技術，
DP步驟:
- 確定狀態：兩個意識，最后一步和子問題，
- 轉移方程：
- 初始條件和邊界情況：
- 計算順序：
/**
* DP Step：
* 1)確定狀態：
* i）簡單說，即開辟一個陣列，陣列中元素代表什么？
* ii）兩個意識：最后一步和子問題
* 2)轉移方程：
* 3)初始條件和邊界情況：
* i)初始條件：轉移方程無法計算，但是實際又需要的
* 4)計算順序：
* 一般是從左往右，從上往下，
*
*/
題目特點：
- 計數：基本操作：加法，
- 求最大最小值：基本操作：min()/max()
- 求存在性：基本操作：AND/OR
/**
* Analyze: 涉及到（1）計數，e.g.,有多少種方式/方法
* （2）求最大最小問題，e.g.,最長上升子序列、最大數字和
* （3）求存在性：e.g.,是否、能不能
* 一般用動態規劃解決，
*/
例題1，求最大最小問題：找零，
package DynamicProgramming;
/**
* Question: 需要付27元錢的賬單，你有2,5,7,三種零錢若干（假使無窮多），
* 問：如何用數目最少的零錢組合就可以支付賬單？
* Analyze: 涉及到 求最大最小問題，基本操作是 min/max
* DP Step：
* 設F(27)表示拼出27的最優組合數目，F(X)表示拼出X的最少硬幣數，
* 1)最后一步：
* 假設需要K枚硬幣，最后一枚是ak，則，前K-1枚拼出了(27-ak).
* 我們知道這（K-1）枚拼出（27-ak）是最優的，
* 但是，我們不知道K是多少，ak是多少？
* 2）子問題：
* 子問題：如何用最少硬幣拼出（27-ak）？
* 原問題：如何用最少硬幣拼出27？
* 將原問題轉化成了規模更小的子問題，
* Wait！！！
* K是多少？ak是多少？
* 雖然我們不知道ak是多少，但是，我們知道ak的取值范圍：2 5 7
* 所以！
* F(27) = min{F(27-2)+1,F(27-5)+1,F(27-7)+1}
* 3）狀態轉移方程：
* F[x] = min{F[x-2]+1,F[x-5]+1,F[x-7]+1}
* 4）邊界情況：
* x-2、x-5、x-7小于0怎么辦？置為無窮大
* 5)初始值：
* F[負數] = INF,F[0] = 0 1->INF:皆可計算
* 6）什么時候停下來？
* 找到27元的最優組合數
* 7）計算順序？
* 因為F[x]依賴于F[x-2],F[x-5],F[x-7]，所以，從左往右計算，
*
*/
public class Coin {
public static final int INF = 1000000007;
public static void main(String[] args){
int total = 27;
// int count = Rec(total); // 遞回版
int count = DP(total); // DP版
System.out.println(count);
}
public static int DP(int money){
// 開辟陣列大小 +1
// 含義：dp[i] 表示湊夠零錢i所需的最少組合數，
int[] dp = new int[money+1];
// 初始化
dp[0] = 0;
// 狀態轉移
for (int i=1;i<=money;i++){
dp[i] = min(dp,i-2,i-5,i-7); // 狀態轉移方程
}
return dp[money];
}
public static int min(int[] a, int i,int j,int k){
int res1 = i<0?INF:(a[i]+1);
int res2 = j<0?INF:(a[j]+1);
int res3 = k<0?INF:(a[k]+1);
return (res1<res2?res1:res2)<res3?(res1<res2?res1:res2):res3;
}
public static int Rec(int money){
/**
* 遞回的程序，可以用遞回樹來模擬：從上往下，從左往右，
*/
if (money==0)
return 0;
if (money==1)
return INF; // 此處為什么不用Integer.MAX_VALUE？因為溢位問題！變成負數，
int res = Integer.MAX_VALUE;
if (money>=2){
res = Math.min(Rec(money-2)+1,res);
}
if (money>=5) {
res = Math.min(Rec(money - 5) + 1, res);
}
if (money>=7) {
res = Math.min(Rec(money - 7) + 1, res);
}
return res;
}
}
例題2，計數問題：走格子，
package DynamicProgramming;
/***
* Question：有一個二維矩陣，機器人從左上角走到右下角，每次只能向右或者向下走，
* 問，機器人有多少種路徑？
* Analyze：計數問題：基本操作是 加法+
* DP Step：
* 1）確定狀態：
* dp[i][j] 含義：機器人走到（i，j）的方法；
* 最后一步：
* 因為最后一步到達(m-1,n-1)，機器人的倒數第二步可能位置：上：(m-2,n-1)，左：(m-1,n-2)
* 則：dp[m-1][n-1] = dp[m-2][n-1]+dp[m-1][n-2]
* 子問題：
* 問：機器人走到(m-2,n-1)，(m-1,n-2)有多少種方法？
* 2）狀態轉移方程：
* dp[i][j] = dp[i-1][j]+dp[i][j-1]
* 3）初始條件和邊界情況：
* 初始條件：dp[0][0] = 1
* i-1、j-1出現負數時，為0.
* 另一種初始化方法：
* 直接把邊界i=0、j=0的時候初始化為1
* 則 dp[1][0]=dp[0][0]+dp[1][-1]=1+0=1
* 機器人走到(m-1,n-1)結束
* 4）計算順序：
* 從左往右，從上往下，
*
*/
public class UniquePaths {
public static void main(String[] args) {
int[][] map = new int[2][2];
int count = uniquePaths(map);
System.out.println(count);
}
public static int uniquePaths(int[][] map){
int count = 0;
map[0][0] = 1;
for (int i=0;i<map.length;i++){
for (int j = 0; j < map[i].length; j++) {
if (i==0&&j==0)
continue;
int up = (i-1<0||j<0)?0:map[i-1][j];
int left = (i<0||j-1<0)?0:map[i][j-1];
map[i][j] = up + left;
// System.out.println(i+","+j+" : "+map[i][j]);
}
}
count = map[map.length-1][map[0].length-1];
return count;
}
}
例題3，存在性問題：青蛙跳躍
package DynamicProgramming;
/**
* Question：跳躍游戲，有n塊石頭，分別在x軸上從0到n-1.一只青蛙從石頭0想跳到石頭n-1.
* 如果，在第i個石頭上，它最多可以跳距離為ai，
* 問：青蛙能否跳到石頭n-1？
* Analyze: 存在性問題，基本操作：OR/AND
* DP Step：
* 1）確定狀態：
* F[i]表示青蛙能否跳到第i個石頭上，
* i）最后一步：
* 最后一步在（n-1）位置，那么上一步呢？
* 假設在第i個位置處，那么能確定嗎？
* 不能，但是i滿足兩個條件：
* condition1：青蛙可以跳到石頭i；
* condition2：青蛙可以從石頭i跳到n-1.
* ii）子問題：
* 青蛙能否跳到石頭i？
* 2）狀態轉移方程：
* F[i] = OR_{0<=j<i}(F[i] AND (F[j]+a[j]>i))
* 3）初始條件和邊界情況
* F[0] = true. 可達
* i = n-1時停止
* 4）計算順序：
* 從左往右，
*/
public class Jump {
public static void main(String[] args) {
int[] ar = new int[]{2,3,1,1,4};
boolean flag = junmp(ar);
System.out.println(flag);
int[] ar1 = new int[]{2,1,1,0,4};
boolean flag1 = junmp(ar1);
System.out.println(flag1);
}
public static boolean junmp(int[] ar){
boolean[] flag = new boolean[ar.length];
flag[0] = true;
for (int i=1;i<ar.length;i++){
for (int j=0;j<i;j++){
if (flag[j] && j+ar[j]>=i){
flag[i] = true;
break;
}
}
}
return flag[ar.length-1];
}
}
練習：HUAWEI 筆試
問題：
有n個中繼器，置于長度為n的線路，（每隔單位距離，放置一個中繼器），中繼器i能傳輸的信號距離由陣列num[i]決定，
問：
從節點0傳到節點n-1，需要的最少中轉次數？
測驗樣例：
輸入：
4
2 3 1 1
輸出：
2
分析：
F[i]：表示信號傳到節點i，所需的最少中轉次數，
1）最后一步：信號從節點k傳到節點n-1.
問題：節點k，如何確定？？？
顯然，節點k要滿足一定條件：即信號可以從節點k傳到節點n-1，
2）子問題：從節點0傳到節點k，需要的最少中轉次數？
3）狀態轉移方程：
F[i] = min{F[k]+1} // k節點 有約束條件，
4）初始化：
F[0] = 1; // 表示從0號節點傳出去，算一次中轉，
5）邊界：信號傳到節點n-1結束，
6）計算順序：從左往右，
package DynamicProgramming;
public class HW03 {
public static void main(String[] args) {
int[] nums = new int[]{3,2,1,1,1};
System.out.println(minNum(nums));
}
public static int minNum(int[] nums){
int[] need = new int[nums.length]; // 表示到達節點i需要的最少中繼器數目
// 初始化
need[0] = 1; // 0號節點出發 第一次中轉
// 狀態轉移
for (int i=1;i<nums.length;i++){
need[i] = Integer.MAX_VALUE;
for (int j = 0; j < i; j++) {
// 判斷中繼器j是否可以到達節點i
if (nums[j]+j>=i){
// 到達節點i可以經過中繼器j
// 比較 是否為最少中轉次數
need[i] = Math.min(need[i], need[j]+1);
}
}
}
return need[nums.length-1];
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/277136.html
標籤：其他
上一篇：第十一屆藍橋杯 ——車牌
下一篇：JAVA初窺-DAY12