牌型种类

一、题目

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

二、方法一:深度优先搜索(dfs)

static int sum = 0; // n代表第n种牌,cartNum代表此时手中牌的总数 public static void dfs(int n, int cartNum) { if (n > 13) {//到了第13种牌，回溯 return; } if (cartNum >= 13) { if (cartNum == 13)//牌数达到13张 sum++; return; } else { dfs(n + 1, cartNum);//第n种牌放0张，开始放下一种牌 dfs(n + 1, cartNum + 1);//第n种牌放1张，开始放下一种牌 dfs(n + 1, cartNum + 2);//第n种牌放2张，开始放下一种牌 dfs(n + 1, cartNum + 3);//第n种牌放3张，开始放下一种牌 dfs(n + 1, cartNum + 4);//第n种牌放4张，开始放下一种牌 } } public static void main(String[] args) { dfs(0, 0);//从0开始代表第一种牌 System.out.println(sum); }

三、方法二:动态规划

设dp[i][j]表示i种牌在牌总数为j时的牌型组合数。 初始状态:在只有1种牌时，不管牌总数有多少均只有一种组合。 dp[i][k]可以由dp[i-1][k]，dp[i-1][k-1]，dp[i-1][k-2]，dp[i-1][k-3]，dp[i-1][k-4]累加得到。(分别对应第i-1种牌放0，1，2，3，4张牌时五种情况)

public static void main(String[] args) { int dp[][] = new int[14][14]; //初始化 dp[1][0] = dp[1][1] = dp[1][2] = dp[1][3] = dp[1][4] = 1; for (int i = 2; i <= 13; i++) {//i代表第几种牌 for (int k = 0; k <= 13; k++) {//k代表牌总数 if (k - 4 >= 0) { dp[i][k] += dp[i - 1][k - 4]; } 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]; } } //打印dp数组 for (int i = 0; i < dp.length; i++) { for (int j = 0; j < dp[i].length; j++) { System.out.print(dp[i][j] + " "); } System.out.println(); } System.out.println(dp[13][13]); }

打印的dp数组: 从上往下代表第i种牌，从左往右代表共j张牌，dp[i][j]即为对应的组合数。

0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 2 3 4 5 4 3 2 1 0 0 0 0 0 1 3 6 10 15 18 19 18 15 10 6 3 1 0 1 4 10 20 35 52 68 80 85 80 68 52 35 20 1 5 15 35 70 121 185 255 320 365 381 365 320 255 1 6 21 56 126 246 426 666 951 1246 1506 1686 1751 1686 1 7 28 84 210 455 875 1520 2415 3535 4795 6055 7140 7875 1 8 36 120 330 784 1652 3144 5475 8800 13140 18320 23940 29400 1 9 45 165 495 1278 2922 6030 11385 19855 32211 48879 69675 93600 1 10 55 220 715 1992 4905 10890 22110 41470 72403 118360 182005 264220 1 11 66 286 1001 2992 7887 18722 40612 81367 151778 265233 436348 678458 1 12 78 364 1365 4356 12232 30888 71214 151580 300366 557712 975338 1613184 1 13 91 455 1820 6175 18395 49205 120055 270270 566280 1111760 2056210 3598180

To strive for a specific aim is the “ideal”.To get something done with one vigorous effort is the “willpower”.The combination of the two is “ambition”.