1079.活字印刷

1.dfs+回溯

解题思路：dfs(len,map,set)表示长度为len的所有可能的序列数。输入序列tiles，对应能够生成的序列的长度大小就有titles.length()种可能。

另外在dfs搜索中，根据Set集合确定当前长度为len的序列的首字母，确定当前位置后，再递归确定长度为len-1的序列的首字母。使用的是Set，所以不需要考虑重复字母导致的重复序列问题。

class Solution {
    public int numTilePossibilities(String tiles) {
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < tiles.length(); i++) {
            map.put(tiles.charAt(i), map.computeIfAbsent(tiles.charAt(i), key -> 0) + 1);
        }
        Set<Character> set = new HashSet<>(map.keySet());
        int res = 0;
        for (int i = 1; i <= tiles.length(); i++) {
            res += dfs(i, map, set);
        }
        return res;
    }

    public int dfs(int len, Map<Character, Integer> map, Set<Character> set) {
        if (len == 0) {
            return 1;
        }
        int sum = 0;
        for (Character character : set) {
            Integer integer = map.get(character);
            if (integer == 0) {
                continue;
            }
            map.put(character, integer - 1);
            sum += dfs(len - 1, map, set);
            //回溯复原
            map.put(character, integer);
        }
        return sum;

    }
}

2.动态规划

以titles=AABCC为例寻找子问题，先来思考，如何计算长为5的序列的数目？由于相同字母不作区分，先考虑2个C如何放置。

问题等价于5个位置选2个放置C的组合方案数，一共10种放法。其余位置放 AAB 三个字符，也就是说剩余要解决的问题为，用 AAB构造长为 3 的序列的数目。这是一个与原问题相似，且规模更小的子问题。

组合数计算

注：(n,k)表示从n个数中选k个数的方案数。即

组合数计算的状态转移公式：。式子的本质是考虑第n个位置【选与不选】，如果选了第n个位置，那么结果就等于从剩下n-1个位置选k-1个的方案数；而如果第n个位置不选，那么结果就等于从剩下n-1个位置选k个的方案数。两者构成该问题解的空间的全集。

DP序列方案数

上面DFS算法中，子问题的思考角度是从当前len长度序列的开头位置该由哪个字符填充出发，状态转换通过逐渐缩减len，最终求解。而此处动态规划考虑的是，把当前第i个字符考虑进去后，能够生成的序列方案数，状态转移是第i个字符参与生成和不参与生成的方案数，类比于组合数计算解空间拆分思想。

定义dp[i][j]：表示考虑前i种字符(不代表生成的序列每一种字符都会用上)，能够构造长度为j的序列的方案数量。设第i个字符在原字符串中有cnt个，状态转移如下：

• 第i个字符不参与生成长度为j的序列，那么dp[i][j]=dp[i-1][j]
• 第i个字符参与生成长度为j的序列，也就是说生成的序列里面一定有第i个字符。如果有k个参与到序列生成，那么需要从j个位置中选k个，放入填充第i种字符。而剩下的j-k个位置，则考虑前i-1种字符来生成。因此。而此处第i个字符使用次数k是不确定的，受到如下约束k<=min(cnt,j)，因此需要枚举来计算总的方案数

因此dp[i][j]状态转移公式为。也可以设置C_n^0=1，将上面两个合并。

边界条件

序列如果全都由第i个字符参与填充，那么前i-1个字符就不需要参与，组合数为1x字符i组合数。因此dp[i-1][0] = 1，不能置为零，否则向数组前面传递结果时，数组当前统计的组合数无效。

public static final int[][] c = new int[8][8];
static {
    for (int i = 1; i <= 7; i++) {
        for (int j = 1; j <= i; j++) {
            if (j == 1) {
                c[i][1] = i;
                continue;
            }
            if (j == i) {
                c[i][i] = 1;
                continue;
            }
            c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
        }
    }
}
public static int numTilePossibilities(String tiles) {
    Map<Character, Integer> map = new HashMap<>();
    for (char c : tiles.toCharArray()) {
        map.put(c, map.getOrDefault(c, 0) + 1);
    }
    Character[] chars = map.keySet().toArray(new Character[0]);
    int[][] dp = new int[map.keySet().size() + 1][tiles.length() + 1];
    for (int i = 1; i < dp.length; i++) {
        //置为1
        dp[i][0] = 1;
        for (int j = 1; j < dp[0].length; j++) {
            int min = Math.min(j, map.get(chars[i - 1]));
            if (j == 1) {
                dp[i][j] = i;
                continue;
            }
            if (i == 1) {
                if (map.get(chars[0]) < j)
                    dp[i][j] = 0;
                else
                    dp[i][j] = 1;
                continue;
            }
            int temp = 0;
            for (int k = 1; k <= min; k++) {
                temp += dp[i - 1][j - k] * c[j][k];
            }
            dp[i][j] = dp[i - 1][j] + temp;
        }
    }
    int ans = 0;
    for (int i = 1; i <= tiles.length(); i++) {
        ans += dp[dp.length - 1][i];
    }
    return ans;
}