dfs 和 dp 初见

第一种方法

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

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

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

题实际可以用搜索去解决,我们把52张牌分成13堆(每堆对应四张点数相同的牌),一堆一堆的随意拿几张牌,不一定要把所有的牌都拿完,只要拿够13张了我们就记录一种牌型,注意前提是要在13堆之内拿够。

*/
#include<cstdio>
#include<algorithm> 
using namespace std;
int cout=0;
void dfs(int i,int k,int t){
    if(i>13){//13堆抽完了 
        return;
    }
    if(t>=13){//手上有13张牌了; 
        if(t==13){
            cout++;
        }
        return;
    }
    dfs(i+1,0,t+0);//下一堆拿0张 
    dfs(i+1,1,t+1);//下一堆拿1张 
    dfs(i+1,2,t+2);//下一堆拿2张 
    dfs(i+1,3,t+3);//下一堆拿3张 
    dfs(i+1,4,t+4);//下一堆拿4张 
} 
int main(){
    dfs(0,0,0);//代表抽第几堆抽牌,抽几张牌,当前手上牌的数目
    printf("%d\n",cout);
    return 0; 

}

第二种方法

动态规划

#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