8.11 動态規劃例題-----鋼條切割(從遞歸--＞ 記憶型遞歸----＞動态規劃)

題目：

已知鋼條總長i 和 每種長度下的鋼條價格，讓我們找到一種切割方案，使得價格最大

解法一：遞歸

import java.util.Arrays;
import java.util.Scanner;

public class Main {
 /* 
  * 思路：假設鋼條長度為L
  * 依次固定前面的切割點為1....L,計算最大價值
  * 
  * 測試資料
10
1 2 3 4 5 6 7 8 9 10
1 5 8 16 10 17 17 20 24 30
  * */
	static int L;//鋼條長度
	static int[] ls;//鋼條的長度
	static int[] ps;//對應長度下的價格
	public static void main(String[] args) {
		//（1）輸入相關資料
		Scanner sc = new Scanner(System.in);
		L= sc.nextInt();
		ls = new int[L];
		ps = new int[L];
		
		for(int i=0;i<L;i++) {//輸入鋼條長度
			ls[i]=sc.nextInt();
		}
		for(int i=0;i<L;i++) {//輸入對應長度下的價格
			ps[i]=sc.nextInt();
		}
		int ans = dfs(L);//從最大長度開始
		System.out.println(ans);
	}
	private static int dfs(int k) {//目前剩餘鋼條的長度k
		if(k==0) {//周遊完所有長度
			return 0;
		}
		int ans=0;
		for(int i=1;i<=k;i++) {//從剩餘長度中依次選擇長度1...K。對應的下标為i-1
			int v = ps[i-1]+dfs(k-i); //截取長度i，從剩餘的k-i長度中繼續查找
			ans = Math.max(ans, v);
		}
		return ans;
	}	
}

           

解法二：記憶型遞歸

import java.util.Arrays;
import java.util.Scanner;

public class Main {
 /* 
  * 思路：假設鋼條長度為L
  * 依次固定前面的切割點為1....L,計算最大價值
  *改進：添加數組rem，用來記錄每種剩餘長度下的最大價值
  * 
  * 測試資料
10
1 2 3 4 5 6 7 8 9 10
1 5 8 16 10 17 17 20 24 30
  * */
	static int L;//鋼條長度
	static int[] ls;//鋼條的長度
	static int[] ps;//對應長度下的價格
	static int[] rem;//記憶數組
	public static void main(String[] args) {
		//（1）輸入相關資料
		Scanner sc = new Scanner(System.in);
		L= sc.nextInt();
		ls = new int[L];
		ps = new int[L];
		
		for(int i=0;i<L;i++) {//輸入鋼條長度
			ls[i]=sc.nextInt();
		}
		for(int i=0;i<L;i++) {//輸入對應長度下的價格
			ps[i]=sc.nextInt();
		}
		
		//初始化rem
		rem = new int[L];
		for(int i=0;i<L;i++) {
			rem[i]=-1;
		}
		int ans = dfs(L);//從最大長度開始
		System.out.println(ans);
	}
	private static int dfs(int k) {//目前剩餘鋼條的長度k
		if(k==0) {//周遊完所有長度
			return 0;
		}
		//（1）計算之前先查找
		if(rem[k-1]>=0) {
			return rem[k-1];
		}
		//(2)計算
		int ans=0;
		for(int i=1;i<=k;i++) {//從剩餘長度中依次選擇長度1...K。對應的下标為i-1
			int v = ps[i-1]+dfs(k-i); //截取長度i，從剩餘的k-i長度中繼續查找
			ans = Math.max(ans, v);
		}
		//（3）計算之後記錄
		rem[k-1] = ans;
		return ans;
	}	
}

           

解法三：動态規劃

代碼：

import java.util.Arrays;
import java.util.Scanner;

public class Main {
 /* 
  * 思路：動态規劃
  * 
  * 測試資料
10
1 2 3 4 5 6 7 8 9 10
1 5 8 16 10 17 17 20 24 30
  * */
	static int L;//鋼條長度
	static int[] ls;//鋼條的長度
	static int[] ps;//對應長度下的價格
	static int[] dp;//存放每種長度下，最大價值
	public static void main(String[] args) {
		//（1）輸入相關資料
		Scanner sc = new Scanner(System.in);
		L= sc.nextInt();
		ls = new int[L];
		ps = new int[L];
		
		for(int i=0;i<L;i++) {//輸入鋼條長度
			ls[i]=sc.nextInt();
		}
		for(int i=0;i<L;i++) {//輸入對應長度下的價格
			ps[i]=sc.nextInt();
		}
		//（2）動态規劃
		dp = new int[L+1];
		dp[0]=0;//長度為0時，價值為0
		for(int i=1;i<=L;i++) {//鋼條長度
			int ans=0;
			for(int j=1;j<=i;j++) {//長度i下，固定長度j
				ans = Math.max(ps[j-1]+dp[i-j], ans); //固定長度j的價格 + （總長度i-固定長度j）的最大價值
			}
			dp[i]=ans;
		}
		//(3)輸出結果
		System.out.println(dp[L]);
	}	
}