當前位置:網站首頁>動態規劃練習——尋找業務限制的嘗試模型,洗咖啡

動態規劃練習——尋找業務限制的嘗試模型,洗咖啡

2022-01-27 10:59:57 愛敲代碼的Harrison

題目

給定一個數組,代錶每個人喝完咖啡准備刷杯子的時間
只有一臺咖啡機,一次只能洗一個杯子,時間耗費a,洗完才能洗下一杯
每個咖啡杯也可以自己揮發幹淨,時間耗費b,咖啡杯可以並行揮發
返回讓所有咖啡杯變幹淨的最早完成時間
三個參數: int[] arr、int a、 int b

注意,咖啡杯雖然可以並行揮發,但是咖啡機只能串行洗杯子,而且一旦杯子决定放入咖啡機洗的話,它就不能自己揮發幹淨了!!!

暴力方法
// drinks 喝完咖啡的時間 固定變量
	// a 洗一個咖啡杯的時間 固定變量
	// b 咖啡杯自己揮發幹淨的時間 固定變量
	// washLine 錶示咖啡機何時可用
	// 0~index-1的杯子都洗幹淨了 
	// index及其往後所有的杯子要洗幹淨 返回最少的時間點
	public static int process(int[] drinks,int a,int b,int index,int washLine) {
    
		if(index==drinks.length-1) {
    
			// 來到最後一個杯子,我可以選擇洗或者讓其自動揮發幹淨
			// 洗的話,喝完這杯咖啡的時間點 和 咖啡機可用的時間點 取最大值,再加上洗杯子的時間
			// 自動揮發,喝完這杯咖啡的時間點 再 加上揮發的時間
			return Math.min(Math.max(drinks[index], washLine)+a, drinks[index]+b);
		}
		// if沒中,剩下不止一杯咖啡
		
		// wash 洗當前這杯咖啡,結束的時間點
		int wash=Math.max(drinks[index], washLine)+a;
		// index+1及其往後所有杯子洗幹淨的時間,不包含index
		int next1=process(drinks, a, b, index+1, wash);
		// index及其往後所有杯子洗幹淨的時間
		// 因為是要等所有杯子都要變幹淨,所以取最大值
		int p1=Math.max(wash, next1);
		
		// dry 當前這杯咖啡揮發幹淨的時間點
		int dry=drinks[index]+b;
		// index+1及其往後所有杯子揮發幹淨的時間,不包含index
		// 自己揮發並不會占用咖啡機
		int next2=process(drinks, a, b, index+1, washLine);
		// index及其往後所有杯子揮發幹淨的時間
		int p2=Math.max(dry, next2);
		
		return Math.min(p1, p2);
	}
動態規劃

從上面暴力嘗試的過程中發現可變參數其實只有兩個,index和washLine。

base case就是index到N-1的時候,所以index的變化範圍是0~N-1

washLine的變化範圍分析不出來,這時候還原到原題意裏面,看看它最誇張的值是多少?washLine最誇張的值就是所有咖啡杯全部都用咖啡機洗的時候!所以這個題是尋找業務限制的嘗試模型。

public static int dp(int[] drinks,int a,int b) {
    
		// 如果洗杯子的時間大於等於杯子自己揮發幹淨的時間
		// 那麼就沒必要洗,也沒必要改動態規劃
		// 最後一杯咖啡揮發的時間就是所有咖啡杯變幹淨的最早完成時間
		int N=drinks.length;
		if(a>=b) {
    
			return drinks[N-1]+b;
		}
		// a<b 才有必要改動態規劃
		// limit 咖啡機何時可用
		int limit=0;
		for(int i=0; i<N; i++) {
    
			// 所有咖啡杯遍曆完成後,limit就是全部洗完的極限
			limit=Math.max(limit,drinks[i])+a;
		}
		int[][] dp=new int[N][limit+1];
		// 填N-1行的所有值
		for(int washLine=0; washLine<=limit; washLine++) {
    
			dp[N-1][washLine]=Math.min(Math.max(drinks[N-1], washLine)+a, drinks[N-1]+b);
		}
		// 填任何一個普遍比特置 從下到上,從左到右
		for(int index=N-2; index>=0; index--) {
    
			for(int washLine=0; washLine<=limit; washLine++) {
    
				int p1=Integer.MAX_VALUE;
				int wash=Math.max(drinks[index],washLine)+a;
				if(wash<=limit) {
    
					p1=Math.max(dp[index+1][wash], wash);
				}
				int p2=Math.max(drinks[index]+b,dp[index+1][washLine]);
				dp[index][washLine]=Math.min(p1, p2);
			}
		}
		return dp[0][0];
	}

完整代碼:

package com.harrison.class13;

public class Code09_Coffee {
    
	// drinks 喝完咖啡的時間 固定變量
	// a 洗一個咖啡杯的時間 固定變量
	// b 咖啡杯自己揮發幹淨的時間 固定變量
	// washLine 錶示咖啡機何時可用
	// 0~index-1的杯子都洗幹淨了 
	// index及其往後所有的杯子要洗幹淨 返回最少的時間點
	public static int process(int[] drinks,int a,int b,int index,int washLine) {
    
		if(index==drinks.length-1) {
    
			// 來到最後一個杯子,我可以選擇洗或者讓其自動揮發幹淨
			// 洗的話,喝完這杯咖啡的時間點 和 咖啡機可用的時間點 取最大值,再加上洗杯子的時間
			// 自動揮發,喝完這杯咖啡的時間點 再 加上揮發的時間
			return Math.min(Math.max(drinks[index], washLine)+a, drinks[index]+b);
		}
		// if沒中,剩下不止一杯咖啡
		
		// wash 洗當前這杯咖啡,結束的時間點
		int wash=Math.max(drinks[index], washLine)+a;
		// index+1及其往後所有杯子洗幹淨的時間,不包含index
		int next1=process(drinks, a, b, index+1, wash);
		// index及其往後所有杯子洗幹淨的時間
		// 因為是要等所有杯子都要變幹淨,所以取最大值
		int p1=Math.max(wash, next1);
		
		// dry 當前這杯咖啡揮發幹淨的時間點
		int dry=drinks[index]+b;
		// index+1及其往後所有杯子揮發幹淨的時間,不包含index
		// 自己揮發並不會占用咖啡機
		int next2=process(drinks, a, b, index+1, washLine);
		// index及其往後所有杯子揮發幹淨的時間
		int p2=Math.max(dry, next2);
		
		return Math.min(p1, p2);
	}
	
	public static int dp(int[] drinks,int a,int b) {
    
		// 如果洗杯子的時間大於等於杯子自己揮發幹淨的時間
		// 那麼就沒必要洗,也沒必要改動態規劃
		// 最後一杯咖啡揮發的時間就是所有咖啡杯變幹淨的最早完成時間
		int N=drinks.length;
		if(a>=b) {
    
			return drinks[N-1]+b;
		}
		// a<b 才有必要改動態規劃
		// limit 咖啡機何時可用
		int limit=0;
		for(int i=0; i<N; i++) {
    
			// 所有咖啡杯遍曆完成後,limit就是全部洗完的極限
			limit=Math.max(limit,drinks[i])+a;
		}
		int[][] dp=new int[N][limit+1];
		// 填N-1行的所有值
		for(int washLine=0; washLine<=limit; washLine++) {
    
			dp[N-1][washLine]=Math.min(Math.max(drinks[N-1], washLine)+a, drinks[N-1]+b);
		}
		// 填任何一個普遍比特置 從下到上,從左到右
		for(int index=N-2; index>=0; index--) {
    
			for(int washLine=0; washLine<=limit; washLine++) {
    
				int p1=Integer.MAX_VALUE;
				int wash=Math.max(drinks[index],washLine)+a;
				if(wash<=limit) {
    
					p1=Math.max(dp[index+1][wash], wash);
				}
				int p2=Math.max(drinks[index]+b,dp[index+1][washLine]);
				dp[index][washLine]=Math.min(p1, p2);
			}
		}
		return dp[0][0];
	}
	
	public static void main(String[] args) {
    
		int[] drinks={
    1,1,5,5,7,10,12,12,12,12,12,12,15};
		int a=3;
		int b=10;
		System.out.println(process(drinks, a, b, 0, 0));
		System.out.println(dp(drinks, a, b));
	}
}

最後,來點方法論的總結:

總的來說以下三條主線非常重要:

1)暴力遞歸改出來後如何優化
2)設計暴力遞歸過程中,如何知道自己設計的東西靠不靠譜
3)根據固定的四個模型,往下編

再强調一下,任何動態規劃都是從最自然智慧的暴力遞歸出發弄出來的!

什麼暴力遞歸可以繼續優化?
有重複調用同一個子問題的解,這種遞歸可以優化。如果每一個子問題都是不同的解,無法優化也不用優化。

暴力遞歸和動態規劃的關系
某一個暴力遞歸,有解的重複調用,就可以把這個暴力遞歸優化成動態規劃。任何動態規劃問題,都一定對應著某一個有解的重複調用的暴力遞歸。但不是所有的暴力遞歸,都一定對應著動態規劃。

面試題和動態規劃的關系
解决一個問題,可能有很多嘗試方法,可能在很多嘗試方法中,又有若幹個嘗試方法有動態規劃的方式。一個問題可能有若幹種動態規劃的解法。

如何找到某個問題的動態規劃方式?
1)設計暴力遞歸:重要原則+4種常見嘗試模型!重點!
2)分析有沒有重複解:套路解决
3)用記憶化搜索->用嚴格錶結構實現動態規劃:套路解决
4)看看能否繼續優化:套路解决

面試中設計暴力遞歸過程的原則
1)每一個可變參數的類型,一定不要比int類型更加複雜
2) 原則1)可以違反,讓類型突破到一維線性結構,那必須是單一可變參數
3)如果發現原則1)被違反,但不違反原則2),只需要做到記憶化搜索即可
4)可變參數的個數,能少則少

知道了面試中設計暴力遞歸過程的原則,然後呢?
一定要逼自己找到不違反原則情况下的暴力嘗試!
如果你找到的暴力嘗試,不符合原則,馬上舍弃!找新的!
如果某個題目突破了設計原則,一定極難極難,面試中出現概率低於5%!

常見的4種嘗試模型
1)從左往右的嘗試模型
2)範圍上的嘗試模型
3)多樣本比特置全對應的嘗試模型
4)尋找業務限制的嘗試模型

如何分析有沒有重複解
列出調用過程,可以只列出前幾層,有沒有重複解,一看便知

暴力遞歸到動態規劃的套路
1)你已經有了一個不違反原則的暴力遞歸,而且的確存在解的重複調用
2)找到哪些參數的變化會影響返回值,對每一個列出變化範圍
3)參數間的所有的組合數量,意味著錶大小
4)記憶化搜索的方法就是傻緩存,非常容易得到
5)規定好嚴格錶的大小,分析比特置的依賴順序,然後從基礎填寫到最終解
6)對於有枚舉行為的决策過程,進一步優化

動態規劃的進一步優化
1)空間壓縮
2)狀態化簡
3)四邊形不等式
其他優化技巧略

暴力遞歸之所以暴力是因為有大量重複計算在浪費時間

動態規劃就是某一類嘗試行為的進一步優化,任何一個動態規劃的問題都是以某一個暴力嘗試過程中優化後的樣子

版權聲明
本文為[愛敲代碼的Harrison]所創,轉載請帶上原文鏈接,感謝
https://cht.chowdera.com/2022/01/202201271059571702.html

隨機推薦