dp動态規劃經典案例

dp動态規劃算法總結

• 基本思想
• • 核心是将一個問題分解成為若幹個子問題
  • 什麼是動态規劃
  • 适用問題
• 案例
• • 爬樓梯
  • 01背包

基本思想

是一種在數學、計算機科學和經濟學中使用的，通過把原問題分解為相對簡單的子問題的方式求解複雜問題的方法。 動态規劃算法是通過拆分問題，定義問題狀态和狀态之間的關系，使得問題能夠以遞推（或者說分治）的方式去解決。

核心是将一個問題分解成為若幹個子問題

什麼是動态規劃

1. 動态規劃（Dynamic Programming）對于子問題重疊的情況特别有效，因為它将子問題的解儲存在表格中，當需要某個子問題的解時，直接取值即可，進而避免重複計算！
2. 動态規劃是一種靈活的方法，不存在一種萬能的動态規劃算法可以解決各類最優化問題（每種算法都有它的缺陷）。是以除了要對基本概念和方法正确了解外，必須具體問題具體分析處理，用靈活的方法建立數學模型，用創造性的技巧去求解。

适用問題

1. 最優化原理：最優解所包含的子問題的解也是最優的，就稱該問題具有最優子結構
2. 無後項性：每個狀态都是過去曆史的一個完整總結（某狀态以後的過程不會影響以前的狀态）
3. 子問題重疊問題：我們必須保證我們分割成的子問題也能按照相同的方法分割成更小的自問題， 并這些自問題的最終分割情況是可以解決的。

案例

爬樓梯

• 題目：有一個樓梯總共n個台階，隻能往上走，每次隻能上1個、2個台階，總共有多少種走法。
  1. 比如，每次走1級台階，一共走10步，這是其中一種走法。我們可以簡寫成 1,1,1,1,1,1,1,1,1,1。
  2. 再比如，每次走2級台階，一共走5步，這是另一種走法。我們可以簡寫成 2,2,2,2,2。
• 分析：假如隻差一步就能走完整個樓梯，要分為幾種情況？因為每一步能走一級或者兩級台階，是以有如下兩種情況： 假設n=10
  1. 最後一步走2級台階，也就是從8級到10級
  2. 最後一步走1級台階，也就是從9級到10級
• 公式：F(n) = F(n-1)+F(n-2) n>2 ; F(n) = n n<=2;

public class Solution {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] dp = new int[n+1];
		for (int i = 0; i <= n; i++) {
			if (i<=2) {
				dp[i] = i;
			}else {
				dp[i] = dp[i-1]+dp[i-2];
			}
		}
		System.out.println(dp[n]);		
	}
}
           

01背包

1. 題目：有n個物品，它們有各自的體積和價值，現有給定容量的背包，如何讓背包裡裝入的物品具有最大的價值總和？
2. 測試案例 capacity=20，N=5， W={2,3,4,5,9}，V={3,4,5,8,10}

public class Solution {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		System.out.print("請輸入背包容器:");
		int capacity = sc.nextInt();
		System.out.print("請輸入物品個數N:");
		int N = sc.nextInt();
		System.out.print("請輸入每個物品的重量:");
		int[] W = new int[N];
		for (int i = 0; i < N; i++) {
			W[i] = sc.nextInt();
		}
		System.out.print("請輸入每個物品的價值:");
		int[] V = new int[N];
		for (int i = 0; i < N; i++) {
			V[i] = sc.nextInt();
		}

		int packageHandle = packageHandle(capacity,N,W,V);
		System.out.println(packageHandle);
	}
	// 01背包處理
	public static int packageHandle(int capacity,int N,int[] W,int[] V) {
		int max = 0;// 最多裝載物品的重量
		int[][] dp = new int[N+1][capacity+1];
		for (int j = 0; j < N; j++) {// 第一個物品數組開始為0，單獨處理
			if (W[0] > j) {
				dp[0][j] = 0;
			}else {
				dp[0][j] = V[0];
			}
		}
		for (int i = 1; i < N; i++) {
			for (int j = 0; j <= capacity; j++) {
				if (W[i]>j) {//如果物品重量大于剩餘重量
						dp[i][j] = dp[i-1][j];
				}else {
					dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-W[i]] + V[i]);
				}
//				max = Math.max(max, dp[i][j]);
			}
		}
		return dp[N-1][capacity];
	}
           

1. 對空間進行優化(将二維數組優化維一維數值)
   • dp找的是前一個狀态，二維數組剛好可以将前一個狀态表現在dp[i-1[j]中，但這樣用了二維數組對空間就不太節約了，是以我們要優化成一維數組是以就需要将前一個狀态弄到一維數組中即找沒有更新的狀态，是以我們可以逆序來找
   • 也就是說将j=n背包容量從最大開始找向前找狀态，前面的狀态都還沒有更新是以就可以繼續用一維數組每次都在一維數組中找到前一個狀态。而如果是按遞增的順序去的化每次j-w[i]都是找到了更新後的狀态，我們要找的上一個狀态，而不是更新後的狀态

public static int opHandle(int capacity,int N,int[] W,int[] V) {
			int[] f = new int[capacity+1];
			for (int i = 0; i < N; i++) {
				for (int j = capacity; j >=W[i]; j--) {
					f[j] = Math.max(f[j],f[j-W[i]] + V[i]);
				}
			}
			return f[capacity];
		}