昨天看到了一句話讓我對(duì)DFS算法有極深的感悟。

這句話就是：DFS有三個(gè)條件：1.最深深度 2.結(jié)束條件 3.如何擴(kuò)展。

其實(shí)對(duì)于1， 2，兩點(diǎn)，感覺不是問題的關(guān)鍵，第三點(diǎn)

才是問題的核心。如何說呢？還是來結(jié)合一個(gè)實(shí)例吧，不然，

很難說清楚。

例題：

有三個(gè)容量分別是A,B,C升的桶，A,B,C分別是三個(gè)從1到20的整數(shù)，

最初，A和B桶都是空的，而C桶是裝滿牛奶的。

有時(shí)，約翰把牛奶從一個(gè)桶倒到另一個(gè)桶中，直到被灌桶裝滿或原桶空了。

當(dāng)然每一次灌注都是完全的。由于節(jié)約，牛奶不會(huì)有丟失。

寫一個(gè)程序去幫助約翰找出當(dāng)A桶是空的時(shí)候，C桶中牛奶所剩量的所有可能性。

解題思路：

每次最多無非有6種倒法，即a->b;a->c;b->a;b->c;c->a;c->b。

所以如果用a、b、c代表三個(gè)桶的容積，x、y、z代表當(dāng)前三個(gè)桶內(nèi)的牛奶數(shù)，

那么不難算出執(zhí)行完a->b后，x變?yōu)?span face="宋體" style="word-wrap: normal; word-break: normal; line-height: 21px; font-family: 宋體">max(0,x+y-b)，y變?yōu)?span face="宋體" style="word-wrap: normal; word-break: normal; line-height: 21px; font-family: 宋體">min(b,x+y)，z不變。

其它倒法類似。

說到這里，思路也就出來了。什么時(shí)候a->b,什么時(shí)候a->c……

這個(gè)就是遞歸的方向的控制了。這個(gè)也是相當(dāng)重要的，因?yàn)椋?/span>

這個(gè)是擴(kuò)展的第一步，如果這一點(diǎn)解決不了，那么就沒有后話了。

其實(shí)這一點(diǎn)是很好控制的，只要a>0, b不滿，就可以實(shí)現(xiàn)a->b了。

其它的6個(gè)倒法也是一樣的。

有了擴(kuò)展的方向以后，遞歸就完成50%，另外的一半就是，在每

個(gè)方向上的具體的參數(shù)變化了，比如本題的x變?yōu)閙ax(0, x+y-b),

y變?yōu)閙in(b, x+y), z不變……，有個(gè)這兩點(diǎn)之后，那么DFS的

核心內(nèi)容也就完成了，一不小心，你就會(huì)AC了。

下面給出核心的代碼。

　　　　　if(a>0 && b<B)  //A向B倒, c不變
		DFS(max(0, a+b-B), min(B, a+b), c);
	if(a>0 && c<C)  //A向C倒，b不變
		DFS(max(0, a+c-C), b, min(C, a+c));
	if(b>0 && a<A)  //B向A倒，c不變
		DFS(min(A, a+b), max(0, b+a-A), c);
	if(b>0 && c<C)  //B向C倒，a不變
		DFS(a, max(0, b+c-C), min(C, b+c));
	if(c>0 && a<A)  //C向A倒，b不變
		DFS(min(A, a+c), b, max(0, a+c-A));
	if(c>0 && b<B)  //C向B倒，a不變
		DFS(a, min(B, b+c), max(0, b+c-B));

6個(gè)if語句就是控制方向的。

DFS中的max, min就是用來控制參數(shù)的變化的。

總結(jié)一下，其實(shí)我一直在強(qiáng)調(diào)“如何擴(kuò)展”這個(gè)方面。

這個(gè)方面又分為兩個(gè)細(xì)節(jié)：

1.擴(kuò)展方向

2.參數(shù)變化

思考一個(gè)DFS題目，要著重在這兩個(gè)細(xì)節(jié)考慮。