特别注意本题中的k-subsequence要求里面的字符各不相同。所以我们就将26个字符的各自美丽值计算出来,目的是从中取出k个,使得美丽值之和最大。这可以用DFS。
另外,其实我们提前将“最大美丽值”计算出来,那必然是将26个美丽值的最大的k个相加。但是我们为什么还要搜索所有的组合呢,因为其中可能有并列的情况。
DFS过程中的优化策略:
- 将count从大到小排列,尽早排除美丽值溢出的情况。
- 当已取字母超过k个时即可停止。
DFS的过程中,每取一个字符,那么subsequence的组合数就乘以该字符的出现次数T(即美丽值),即在这么多相同的字符里选择一个,就有T种选法。