[数据结构与算法]蓝桥杯2015年第六届真题-牌型种类

题目

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

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

题解

dfs 或 动态规划 都可。

每种牌被拿到的可能无非就四种，拿到一张、拿到两张、拿到三张或拿到四张。

直接看代码吧，代码比较好理解。

代码

dfs 代码

#include<bits/stdc++.h>
using namespace std;

int ans = 0;

void dfs (int have, int kind) { // have表示已经拿到几张手牌了；kind表示递归的深度，也表示枚举到了第几种牌了
	if (have == 13 || kind > 13) {
		if (have == 13) ans ++; // 如果手中有13张牌了，说明到达一种合理的情况
		return ; // 如果只是枚举完了13种牌型，那么不算到达合理情况，所以会直接返回
	}
	for (int i = 0;i <= 4;i ++) // 枚举手中拥有当前牌型的牌的个数
		dfs (have + i, kind + 1);	
}

int main()
{
	dfs (0, 1);	// 初始手中牌数为0，从第一种牌型开始枚举

	cout << ans << endl;
	return 0;
}

动态规划代码

#include <iostream>
using namespace std;
 
int dp[14][14]; // dp[i][j]表示手中的j张牌由前i种牌型的牌构成的方案数
 
int main() {
    dp[1][0] = dp[1][1] = dp[1][2] = dp[1][3] = dp[1][4] = 1; // 初始化，只有一种牌型时无论几张都只有一种方案
 
    for (int i = 2; i <= 13; i++) { // 枚举牌型
        for (int k = 0; k <= 13; k++) { // 枚举手牌数
            if (k - 4 >= 0) dp[i][k] += dp[i-1][k-4]; // 如果手牌数大于4，则可以选择拿四张第i种牌型的牌
            if (k - 3 >= 0) dp[i][k] += dp[i-1][k-3]; // 与上面类似
            if (k - 2 >= 0) dp[i][k] += dp[i-1][k-2];
            if (k - 1 >= 0) dp[i][k] += dp[i-1][k-1];
            dp[i][k] += dp[i-1][k]; // 第i种牌型的牌一张也不拿
        }
    }
 
    cout << dp[13][13] << endl; 
    return 0;
}

答案：3598180