最少出牌次数

QW是一名打牌小能手，现在他手里有n张牌，给定数组cards表示QW牌的点数,牌的点数范围为1~9，他想要用尽量少的次数把牌出完，请输出QW最少出牌次数
QW有以下三种出牌方式:
1.打出任意一张牌
2.打出两张及以上相同点数的牌
3.打出至少5张点数连续的牌(2,3,4,5,6是合法的而3,3,4,5,6,7是不合法的)

除了bf，想不到什么好的办法。。， 有思路的朋友麻烦给个提示，谢谢。

没有人吗？

特别不擅长这种题

加入一个STATE【】每个组合、最小花费 怎么样？这样可以prune掉一些更多的花费。

把所有的牌区分开来。按照至少5张点数连续的牌这一规则，说明其它牌和这些都不连着，可以单独BF处理。包括重复比如2,2,3,4,4,4,5,5,5,6,6,6,7可以计算出最小花费。每个区域的最小值加起来就是整体的最小值。
另外这个问题可以继续深化。比如
2,2,3,4,4,4,5,5,5,6,6,6,7
和
4,4,5,6,6,6,7,7,7,8,8,8,9
转化为A:2, B:1, C: 3, D: 3, E: 3, F: 1是同一个问题。也可以记忆。

递归关系。如果我打444，那么成本就转化为f(223)+f(5556667)+1

补充内容 (2019-1-24 03:52):
如果能够利用规则二和三，则不把规则一加入BF中。

基本上是暴力bfs， 先bucket，然后就慢慢搜。你会发现time limit 超时，这个时候你引入一个规则，就是如果不出顺子，比如把那张牌全出完。然后你的程序就过了。

我原来想是贪心做，就是先打顺子，再打重复的，最后打单张，单手这样想有错误，lintcode86%的数据可以通过但是还有14%通过不了，看来要BFS试一试了

crlyw 发表于 2019-1-30 05:36
我原来想是贪心做，就是先打顺子，再打重复的，最后打单张，单手这样想有错误，lintcode86%的数据可以通过 ...

请问利口猿啼号 是。。。 ？

crlyw 发表于 2019-1-30 05:36
我原来想是贪心做，就是先打顺子，再打重复的，最后打单张，单手这样想有错误，lintcode86%的数据可以通过 ...

感觉是标准BFS。

Scala688 发表于 2019-1-30 06:04
请问利口猿啼号 是。。。 ？

这个是lintcode的1672题，但是是ladder的好像搜索不到