DP category
总结一下组合数DP公式
之前APAC Round2 ProA题，给定M种字符，问N个字符的排列有多少，其中每个字符至少1次。
f(m, n) 含义先往题意靠，m表示m种，n表示前n个位置，
f(m-1, n) 表示m-1种放在n个位置，这个显然不行，因为没有放满m种字符，
f(m, n-1) 表示m种放在前n-1个位置，那么最后一个位置任意放一种，m*f(m, n-1)
f(m-1, n-1) 表示m-1种放在前n-1个位置，那么最后一个位置只能放最后一种，而哪前m-1种呢，C(m, m-1)
故dp： f(m,n)=mf(m,n-1)+mf(m-1,n-1)
n个不同的数划分为m个无标签的非空集合(第二类Striling数)
n-1个数划分了m-1个非空集合，则最后一个数必须单独成集合，f(n-1, m-1)
n-1个数划分了m个集合，最后一个数随机丢进一个，f(n-1, m)*m,
n个数划分了m-1个集合，不成立
f(n, m)=f(n-1, m-1) + m*f(n-1,m)
n个不同的数划分为m个有标签的非空集合
n-1个数划分了m-1个非空集合，则最后一个数必须单独成集合，但m-1个集合有标签，C(m, m-1)f(n-1, m-1)
n-1个数划分了m个集合，最后一个数随机丢进一个，f(n-1, m)m,
n个数划分了m-1个集合，不成立
f(n, m)=mf(n-1, m-1) + mf(n-1,m)