英文原文
中文题目
给定若干数字作为麻将牌的数值（记作一维数组 tiles），请返回所给 tiles 最多可组成的牌组数。
注意：凑成牌组时，每张牌仅能使用一次。
示例 1：
输入：
tiles = [2,2,2,3,4]输出：
1解释：最多可以组合出 [2,2,2] 或者 [2,3,4] 其中一组牌。
示例 2：
输入：
tiles = [2,2,2,3,4,1,3]输出：
2解释：最多可以组合出 [1,2,3] 与 [2,3,4] 两组牌。
提示：
1 <= tiles.length <= 10^51 <= tiles[i] <= 10^9
通过代码
高赞题解
原作者：@lucifer1004
原回答：【DP】为什么每种牌最多留4张？
第一步：整理牌序
首先，将 tiles 变为 map<int, int>。其中，键是点数, 而值是对应的牌数，C++中的map是按照键从小到大排列的。
map<int, int> count;
for (auto tile : tiles)
count[tile]++;接下来，我们的指针会跟随点数 [tile] 移动，动规数组也会随着 [tile] 更新。
第二步：状态矩阵
动规的目标毫无疑问：已知之前所有牌面最高得分（记为dp），当指针随着点数增加时，我们要根据新增加的牌来更新最高得分（记为dp）。
例如，在下面这副牌中，假设现在我们遍历到 [tile] = 4，我们需要根据4的牌数来更新得分。即
dp += 新增得分
新增加的得分有两部分：
4和之前两张牌组成的顺子得分，4自己组成的刻子得分。
仔细分析我们发现，有两种不同的情况。
- 情况1
之前组成了两副顺子，留下来 1 张[2]和 0 张[3]，无法和[4]一起组成新的顺子。因此，新增加的[4]只带来了 1 分新得分：[4] 的刻子得分。
- 情况2
之前组成了一副顺子和一副刻子，留下来 2 张[2]和 1 张[3]，能够[4]一起组成新的顺子。另外，剩下的[4]也能组成一副刻子 。因此，新增加的[4]最多能带来 2 分：一分顺子， 一分刻子。
仔细分析这两种情况：我们发现：
影响新增得分的只有[2]和[3]的剩余牌数，也就是[tile-2]和[tile-1]的剩余牌数。
因此，我们的dp应该是一个二维数组，dp[cnt_2][cnt_1] 表示：在预留 cnt_2 张 [tile-2] 和 cnt_1 张 [tile-1] 的前提下，[tile] 之前的牌能组成的牌组数。
第三步：压缩状态空间
如果我们把预留数量的所有可能性都列出来，dp的大小将有$O(n^2)$。因此，我们考虑限制预留的牌数。
预留的牌仅用于跟下两张牌组成顺子，故应考虑限制顺子的数量。如下图所示，当相同顺子的数量大于等于3时，我们可以把每3副顺子换成3副对应的刻子。
那么，相同顺子的数量<=2副。
如下图所示，为[5]预留的牌，在未来遍历到[6]时，可组成顺子([4], [5], [6])；在未来遍历到[7]时，可组成顺子([5], [6], [7])。
每种顺子不超过2副。因此，我们预留的牌，也不超过4张。
dp的空间就压缩到了dp[0~4][0~4]，即$O(5^2)$（因为还要考虑一张都不留的情况）。
第三步：状态转移方程
根据前面的分析，我们知道，每一步的分数由三部分组成：
- 之前赚的分数；
[tile-2]、[tile-1]和[tile]组成的顺子得分；[tile]自己组成的刻子得分。
注意到，我们当前的 [tile] 也不要一次性用完，也要考虑留下几张跟后面的牌组成顺子。
那么，我们应该怎么规划顺子得分、刻子得分和预留的牌数呢？我们通过遍历的方式把所有的可能性罗列出来。
<
,
,
,
,
,
,
,
,
,
,
>
罗列顺子的所有可能性
首先，我们把顺子数量从0开始罗列。
正如前文所述，我们预留了cnt_2张[tile-2] 和 cnt_1张[tile-1]，而现在我们有 cnt张新增加的[tile]牌。
组成的顺子数量，不能超过 cnt_2、cnt_1、cnt 的任何一个。
for (int shunzi = 0; shunzi <= min(cnt_2, min(cnt_1, cnt)); ++shunzi) {
...对于下一个点数而言，[new_tile-2] 就是当前的 [tile-1]，我们用new_2 代表预留的 [new_tile-2] 的牌数，这个牌数就是[tile-1]的牌数减去顺子数量。
例如，在下面这张图中，下一个点数[new_tile]是5，new_1是预留的[4]的数量，new_2就是剩下的[3]的数量。原来我们有 3 张[3]，顺子用掉 2 张，就还剩 1 张。
int new_2 = cnt_1 - shunzi;罗列预留牌数的所有可能性
同样的，我们把当前预留的牌数从0开始罗列。
对于下一张牌而言，当前的牌面自然是 [new_tile-1] 了，所以我们用 new_1 代表预留的 [new_tile-1] 的牌数，预留的牌数自然不能超过[tile]的牌数减去顺子用掉的数量。
for (int new_1 = 0; new_1 <= cnt - shunzi; ++new_1) {
...那么，自然地，去掉了顺子数量和预留牌数之后，剩下的 [tile] 的数量全部组成刻子，它的得分是：(cnt - shunzi - new_1) / 3。
综上所述，新的得分是三者相加，即
int new_score = dp[cnt_2][cnt_1] + shunzi + (cnt - shunzi - new_1) / 3;第四步：找到最高分
全部遍历完成后，我们搜索并返回dp的最大值：
int ans = 0;
for (int cnt_2 = 0; cnt_2 < 5; ++cnt_2)
for (int cnt_1 = 0; cnt_1 < 5; ++cnt_1)
ans = max(ans, dp[cnt_2][cnt_1]);
return ans;最终程序
本程序改编自@lucifer1004 的解答。更改了变量命名，使之更容易被理解。如有错误请指正。
class Solution {
public:
int maxGroupNumber(vector<int>& tiles) {
map<int, int> count; // [点数, 对应的牌数]，C++中的map是按照key(点数)从小到大排列的。
for (auto tile : tiles)
count[tile]++;
// dp[x][y] 表示
// 在预留x张 [tile-2] 和y张 [tile-1] 的前提下，
// [tile] 之前的牌能组成的牌组数
vector<vector<int>> dp(5, vector<int>(5, -1));
dp[0][0] = 0;
int prev_tile = 0; // 前一张牌的点数
for (auto [tile, cnt] : count) { // [tile表示当前点数, cnt表示对应的牌数]
// 如果上一张牌和这张牌没法连起来
// 意味着无论之前留几张牌，都无法和tile一起组成顺子，因此，只保留dp[0][0]的情形。
if (prev_tile != tile - 1) {
// dp[0][0] 表示，之前留下的 “tile-2点的牌数” 和 “tile-1点的牌数” 都为0
int dp00 = dp[0][0];
// dp[x][y] == -1 表示，之前没有 “留下x张[tile-2]点的和y张[tile-1]点” 的情况
dp = vector<vector<int>>(5, vector<int>(5, -1));
dp[0][0] = dp00;
}
// 新的dp数组
vector<vector<int>> new_dp(5, vector<int>(5, -1));
for (int cnt_2 = 0; cnt_2 < 5; ++cnt_2) // [tile-2] 的牌数
for (int cnt_1 = 0; cnt_1 < 5; ++cnt_1) { // [tile-1] 的牌数
// 如果之前没有留下这么多张牌
if (dp[cnt_2][cnt_1] < 0)
continue;
// 顺子数量不能超过[tile-2]、[tile-1]、[tile]的牌数
for (int shunzi = 0; shunzi <= min(cnt_2, min(cnt_1, cnt)); ++shunzi) {
int new_2 = cnt_1 - shunzi; // 对于下一个点数 new_tile = tile + 1 而言，
// [new_tile - 2] 就是当前的 [tile - 1]
// new_2 代表预留的 [new_tile - 2] 的牌数
// 也就是当前的 [tile - 1] 的牌数 - 顺子数量
// 同理，对于下一个点数 [new_tile] 而言，new_1 代表预留的 [new_tile - 1] 的牌数，
// 也就是预留的 [tile] 的数量。
// 预留的数量不超过四张，也不超过 ( [tile]的牌数 - 顺子数量 )
for (int new_1 = 0; new_1 <= min(4, cnt - shunzi); ++new_1) {
// 新的牌组数等于以下三者相加：
// 1. dp数组保存的，留下 cnt_2 张 [tile-2] 和 cnt_1 张 [tile-1] 的前提下，tile-1 之前的牌面能凑出来的牌组数
// 2. 顺子数量
// 3. [tile] 组成的刻子数量 = ( [tile] - 顺子数量 - 留下备用的牌 ) / 3
int new_score = dp[cnt_2][cnt_1] + shunzi + (cnt - shunzi - new_1) / 3;
new_dp[new_2][new_1] = max(new_dp[new_2][new_1], new_score);
}
}
}
// 将new_dp数组赋值给dp数组
dp = move(new_dp);
// 将当前tile记录都上一个tile中
prev_tile = tile;
}
// 找到并返回dp的最大值
int ans = 0;
for (int cnt_2 = 0; cnt_2 < 5; ++cnt_2)
for (int cnt_1 = 0; cnt_1 < 5; ++cnt_1)
ans = max(ans, dp[cnt_2][cnt_1]);
return ans;
}
};顺带分享一道类似问题：
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 836 | 3118 | 26.8% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
