题目描述

你有一套活字字模 tiles，其中每个字模上都刻有一个字母 tiles[i]。返回你可以印出的非空字母序列的数目。

注意：本题中，每个活字字模只能使用一次。

示例 1：

输入：“AAB”
输出：8
解释：可能的序列为 “A”, “B”, “AA”, “AB”, “BA”, “AAB”, “ABA”, “BAA”。
示例 2：

输入：“AAABBC”
输出：188
示例 3：

输入：“V”
输出：1

提示：

1 <= tiles.length <= 7
tiles 由大写英文字母组成

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/letter-tile-possibilities
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

分析

动态规划
定义dp[i][j]表示前i种字符构成长度为j的字符串的序列的方案数
初始化dp[0][0]=1表示构成空字符串的方案数为1种
状态转移：
对于第i种字符我们可以不选它构成长度为j的字符串
此时dp[i][j]=dp[i-1][j]。
我们可以选择第i种字符来构成长度为j的字符串
其中第i种字符的总数量为cnt，那么我们可以选择k个第i种字符去构成长度为j的字符串，k属于[0，min（j，cnt）]。其中选0个等价于不选它，构成的字符串长度为j，而第i种字符最多有cnt个，所以最多可以选min（j，cnt）个第i种字符。
选择的这k个字符需要在长度为j的字符串中存在，则这k个字符在字符串中的位置方案一共有C[j,k]种。
C[j,k]指概率c公式是：C（n，k）=n（n-1）（n-2）(n-k+1)/k!
dp[i][j]+=dp[i-1][j-k]*C(j,k);
最终结果就是所有选取种类的字符构成长度为1，2…tiles.length的方案数总和。

代码

class Solution {public int numTilePossibilities(String tiles) {HashMap<Character,Integer> map=new HashMap<>();HashSet<Character> set=new HashSet<>();//统计字符出现的次数for(char c:tiles.toCharArray()){if(map.containsKey(c)==false){map.put(c,1);}else{map.put(c,map.get(c)+1);}set.add(c);}int m=set.size();int n=tiles.length();int[][] dp=new int[m+1][n+1];dp[0][0]=1;int i=1;for(char c:set){//选取前i种字符int cnt=map.get(c);//第i种字符的个数for(int j=0;j<=n;j++){//构成长度为j的字符串for(int k=0;k<=j && k<=cnt;k++){//状态转移，选取k个第i种字符dp[i][j]+=dp[i-1][j-k]*get(j,k);}}i++;}int ans = 0;for (int j = 1; j <= n; j++)ans += dp[m][j];return ans;}//C（j，k）=j（j-1）（j-2）(j-k+1)/k!public int get(int j,int k){int fenzi=1;int fenmu=1;for(int i=0;i<k;i++){fenzi*=(j-i);fenmu*=(k-i);}return fenzi/fenmu;}
}