深度優先搜尋之牌型種類

1. 問題描述：

小明被劫持到X賭城，被迫與其他3人玩牌。

一副撲克牌（去掉大小王牌，共52張），均勻發給4個人，每個人13張。

這時，小明腦子裡突然冒出一個問題：

如果不考慮花色，隻考慮點數，也不考慮自己得到的牌的先後順序，自己手裡能拿到的初始牌型組合一共有多少種呢？

請填寫該整數，不要填寫任何多餘的内容或說明文字

2. 思路分析：

① 我們分析題目可以知道這是一種典型的組合問題，一般是使用遞歸的方法去解決，可以使用深度優先搜尋去解決，我們先可以這樣想，因為總共有13種類型的牌，對于每一種類型的牌我都嘗試去拿k張，當發現相同的牌有四張的時候這個時候就不能夠拿了，是以需要使用一個動态的List<String>來進行記錄之前拿過的牌，可以使用一個方法傳入目前正在周遊到牌的類型，這樣在方法中進行判斷并且計數看一下目前選擇的牌數量是否等于了4假如等于了4continue直接考慮下一種類型的牌，這裡使用List來進行記錄的原因是使用其他類似于String類型的來記錄非常不友善，因為字元串拼接起來之後不知道哪和哪了，是以需要List來進行記錄

② 當發現我們拿取的牌的數量等于了13之後那麼我們就可以計數加1然後直接傳回了，但是這樣做的話每一層的話都是展開13次來進行搜尋這樣的話接近于13的13次方資料規模是相當龐大的是以運作之後是計算不出來答案的

具體的代碼如下：

import java.util.ArrayList;
import java.util.List;
public class Main {
	static int count = 0;
	//使用動态數組的話比較好處理字元串的問題
	static List<String> rec = new ArrayList<String>();
	public static void main(String[] args) {
		String arr[] = new String[13];
		for(int i = 0; i < 13; i++){
			arr[i] = Integer.toString(i);
		}
		dfs(arr, 0);
		System.out.println(count);
	}
	
	private static void dfs(String[] arr, int k) {
		if(k == 13){
			count++;
			return;
		}
		for(int i = 0; i < 13; i++){
			if(countOf(i + 1) == 4) continue;
			rec.add(Integer.toString(i + 1));
			dfs(arr, k + 1);
			//回溯把之前加進去的删除掉
			rec.remove(rec.size() - 1);
		}	
	}

	private static int countOf(int i) {
		int cnt = 0;
		for(int k = 0; k < rec.size(); k++){
			if(rec.get(k) == Integer.toString(i)) cnt++;
		}
		return cnt;
	}
}
           

3. 除了上面這樣的想法，我們還可以這樣想對于13種類型的牌，對于每一種牌來說我們都是有5種選擇，分别是拿取0,1,2,3,4張牌，對于13個位置我們都是具有這樣的選擇，是以資料規模相當于5的13次方資料規模大但是還是可以計算出來的，考慮到這裡，我想到之前我解決過的在m個相同的球中選擇n個球的方法問有多少種選擇的方案這個問題是很類似的，本質上是一樣的，對于取球的問題我們可以使用數組來記錄目前位置的球有多少個，然後使用深度優先搜尋算法，嘗試每一個位置去拿取0到目前位置能夠取球的最大數量，是以這兩個問題本質上是一樣的，都是組合問題，都可以使用上面這種考慮每一個位置可以拿取多少張的牌和每一個位置我能夠拿取多少個球

總結一下：與之前的逐漸生成13張牌的過程來說，同樣是深度優先搜尋，但是時間複雜度完全不是在等級上的，第二種的方法可以在1秒鐘之内計算出來，是以來說考慮問題的方向不同那麼最終能夠可以解決的問題也是不一樣的

4. 具體的代碼如下：

public class Main {
	static int count = 0;
	public static void main(String[] args) {
		dfs(0, 0);
		System.out.println(count);
	}
	
	private static void dfs(int k, int cur) {
		if(k == 13 && cur == 13){
			count++;
			return;
		}
		if(cur > 13 || k == 13) return;
		for(int i = 0; i < 5 && cur + i <= 13; i++){
			dfs(k + 1, cur + i);
		}
	}
}