牌型种数问题--二维动态规划解决（附DFS）

0x01.问题

小明被劫持到X赌城，被迫与其他3人玩牌。  
一副扑克牌（去掉大小王牌，共52张），均匀发给4个人，每个人13张。  
这时，小明脑子里突然冒出一个问题：  
如果不考虑花色，只考虑点数，也不考虑自己得到的牌的先后顺序，自己手里能拿到的初始牌型组合一共有多少种呢？

请填写该整数，不要填写任何多余的内容或说明文字。

注：该题是蓝桥杯2015初赛第7题，为填空题。

0x02. 分析问题

要求组合的种数，我们首先要清楚扑克牌在题目中的特点：

1. 不计花色，只计点数。
2. 一个点数的可能有五种，即有0，1，2，3，4五种可能。
3. 总共拿到手的牌有13张。

于是我们的暴力枚举法就诞生了，方法就是13个for循环，每个循环都从0到4，最内层的条件是所有牌的总数为13。

这个耗时似乎有点长，在我的电脑上大概耗时3秒。

当然，这个肯定不是这个问题的最好解决办法，我发现，用动态规划可以巧妙的解决这个问题。

0x03.动态规划

动态规划(Dynamic Programming)这个简介就不说了，说白了就是，在有一定初始条件的情况下，根据一些递推的关系式，不断的往前或者往后推导，最后得到想要的答案。

运用动态规划，需要满足两个条件：

1. 有一定的初始条件。
2. 能找到合适的递推关系式。

0x04.动态规划解决此问题

首先，我们应该确定的是采用何种结构去把这个问题表示清楚。

13张牌，拿到每一张牌后，手中的手牌数有13种可能，我们可以用二维数组表示出这个关系：

DP[i][j]  表示拿到第 i 张牌，此时手中有 j 张牌的可能组合数。

寻找初始条件：很明显，初始条件就是，拿到第一张牌的时候，手中最多有4张牌，组合是都是1。

也就是  DP[1][0]=DP[1][1]=DP[1][2]=DP[1][3]=DP[1][4]=0。

递推条件就是，根据手中牌的数目，加上之前相同手牌数的可能组合数，然后加上'''加上这张牌能够对前一次手牌的解数产生影响的解数'''。

最终的答案就是 DP[13][13] 的值。

0x05.代码

#include<stdio.h>

int main()
{
	int i, j;
	long DP[14][14];
	for (i = 1; i <= 13; i++)
	{
		for (j = 0; j <= 13; j++)
		{
			DP[i][j] = 0;
		}
	}
	for (i = 0; i <= 4; i++)//动态规划的初始条件
	{
		DP[1][i] = 1;
	}
	for (i = 2; i <= 13; i++)
	{
		for (j = 0; j <= 13; j++)
		{
			DP[i][j] += DP[i - 1][j];//加上同牌数解数
			if (j >= 1)
			{
				DP[i][j] += DP[i - 1][j - 1];//加上一张牌的解数
				if (j >= 2)
				{
					DP[i][j] += DP[i - 1][j - 2];//加上两张牌的解数
					if (j >= 3)
					{
						DP[i][j] += DP[i - 1][j - 3];//加上三张牌的解数
						if (j >= 4)
						{
							DP[i][j] += DP[i - 1][j - 4];//加上四张及以上的解数
						}
					}
				}
			}
		}
	}
	printf("%ld", DP[13][13]);//最终解
}

答案是：3598180

0x06.附--其它解法--DFS

深度优先搜索的解法如下：

#include<stdio.h>
int ans = 0, sum = 0;
void DFS(int cur)//cur为手中牌数
{
    if (sum>13)return;
    if (cur == 13)
    {
        if (sum == 13)ans++;
        return;
    }
    else
    {
      for (int i = 0; i < 5; i++)
        {
            sum += i;
            DFS(cur + 1);
            sum -= i;//还原状态
        }
    }
}

int main()
{

    DFS(0);
    printf("%d",ans);
}