好子集的数目
好子集的数目
30以内的质数有十个：{2,3,5,7,11,13,17,19,23,29}
算术基本定理，大于1的正整数可以分解成若干个质因数的乘积，所以30以内的数可以分为3类：
+ 1
+ 分解成若干质因数乘积，每一个质因数都唯一出现一次，状压
+ 分解成若干质因数乘积，存在质因数次数>1 即i%(prime*prime)==0
class Solution {
public int numberOfGoodSubsets(int[] nums){
int MOD=1000000007;
int[] primes={2,3,5,7,11,13,17,19,23,29};
//对每一个数次数统计
int[] freq=new int[31];
for (int num : nums) {
freq[num]++;
}
//dp[i][j]:表示[2:i]个元素,质因数的状态为j的好子集数目
int[][] dp=new int[31][1<<10];
//初始化
dp[1][0]=1;
for(int i=0;i<freq[1];i++){
dp[1][0]=dp[1][0]*2%MOD;
}
for(int i=2;i<=30;i++){
for(int j=0;j<(1<<10);j++){
dp[i][j]=dp[i-1][j];//前i个元素,质数的状态为j,对于第i个元素选与不选最少都是dp[i-1][j],如果可以选,加上选择的方案数
}
if(freq[i]==0){
continue;//集合中没有该元素
}
boolean check=true;
int subset=0;int x=i;
for(int j=0;j<10;j++){
int prime=primes[j];
if(x%(prime*prime)==0){
check=false;
break;
}
if(x%prime==0){
subset|=(1<<j);
}
}
if(!check){
continue;
}
for(int mask=1;mask<(1<<10);mask++){
if((mask&subset)==subset){
dp[i][mask]=(int)((dp[i-1][mask]+((long)dp[i-1][mask^subset])*freq[i])%MOD);
}
}
}
int res=0;
for(int mask=1;mask<(1<<10);mask++){
res=(res+dp[30][mask])%MOD;
}
return res;
}
}
不同的好子序列的数目
不同的好子序列的数目
定义dp[i][0]:表示前i个字符中以0结尾的合法子序列数目
dp[i][1]:表示前i个字符中以1结尾的合法子序列的数目
class Solution {
public int numberOfUniqueGoodSubsequences(String binary) {
int MOD=1000000007;
//定义dp[i][0]:表示前i个字符,以0结尾的子序列的个数
//dp[i][1]:表示前i个字符,以1结尾的子序列的个数
int n=binary.length();
int[][] dp=new int[n+1][2];
boolean flag=false;
for(int i=1;i<=n;i++){
if(binary.charAt(i-1)=='1'){
dp[i][0]=dp[i-1][0]%MOD;
dp[i][1]=(dp[i-1][0]%MOD+dp[i-1][1]%MOD+1)%MOD;
}else{
flag=true;
dp[i][1]=dp[i-1][1]%MOD;
dp[i][0]=(dp[i-1][0]%MOD+dp[i-1][1]%MOD)%MOD;
//不需要加1的原因当前单独的0不能构成合法的序列,否则后面的dp[k][0]会出现00非法序列
}
}
//判断是否存在0
return (dp[n][0]+dp[n][1]+(flag? 1:0))%MOD;
}
}
划分数字的方案数
划分数字的方案数
定义dp[i][j]表示前j个字符元素，最后一个数的开始位置为i,i+1,i+2,…j
class Solution {
public int numberOfCombinations(String num) {
int MOD=1000000007;
//定义dp[i][j]表示前j个字符对于 最后一个数为起始数位为i,i+1,i+2,...,j
if (num.charAt(0) == '0') {
return 0;
}
int n=num.length();
int[][] lcp=new int[n][n];//lcp[i][j]表示i开始的倒数第二个数与j开始的倒数第一个数最长公共前缀
//初始化
for(int i=n-1;i>=0;i--){
lcp[i][n-1]=(num.charAt(i)==num.charAt(n-1))? 1:0;
}
//从后往前递推
for(int i=n-2;i>=0;i--){
for(int j=n-2;j>i;j--){//j=n-1已经初始化了
lcp[i][j]=(num.charAt(i)==num.charAt(j)? lcp[i+1][j+1]+1:0);
}
}
//定义状态转移
int[][] dp=new int[n][n];
//初始化
for(int i=0;i<n;i++){
dp[0][i]=1;
}
for(int i=1;i<n;i++){
if (num.charAt(i) == '0') {//最后一个数的起始位置
continue;
}
int prefix=0;
for(int j=i;j<n;j++){
int length=j-i+1;
dp[i][j]=prefix;
if (i >= length) {//倒数第二个数存在
if(lcp[i-length][i]>=length||num.charAt(i-length+lcp[i-length][i])<num.charAt(i+lcp[i-length][i])){
dp[i][j]=(dp[i][j]%MOD+dp[i-length][i-1]%MOD)%MOD;
}
prefix=(prefix%MOD+dp[i-length][i-1]%MOD)%MOD;
}
}
}
int res=0;
for(int i=0;i<n;i++){
res=(res%MOD+dp[i][n-1]%MOD)%MOD;
}
return res;
}
}
从子集的和还原数组
从子集的和还原数组
确定一个元素的一种方式：对于所有子集和中的最大元素a与次大元素b
a-b一定是一个绝对值较小的元素，d -d 或者同时存在d -d
对于没确定一个元素d或-d 需要将所有的剩下n-1个元素的所有的子集和S 筛选出来进行dfs(n-1,ans,S)
筛选的方式是通过对于每一个元素d n个元素的所有的子集和可以分为2^(n-1)个元素的包含d的子集和；不包含d的2^(n-1)个子集和
筛选的方式是，两个集合中的原始存在一一对应的关系，
将数组元素先进行排序，通过从小到大进行遍历每一个元素，如果该元素没有配对，分别将两个元素a a+d加入两个集合，并将配对的元素进行标记
class Solution {
public int[] recoverArray(int n, int[] sums) {
List<Integer> ans=new ArrayList<Integer>();
Arrays.sort(sums);
dfs(n,ans,sums);
int[] res=new int[ans.size()];
for(int i=0;i<ans.size();i++){
res[i]=ans.get(i);
}
return res;
}
public boolean dfs(int n,List<Integer> ans,int[] sums){
if(n==0){//已经没有子集可以确定了
return true;
}
int d=sums[(1<<n)-1]-sums[(1<<n)-2];
int mask=0;
//所有的子集一定存在一个元素为d或者-d;通过mask进行标记
for (int sum : sums) {
if(sum==d){
mask|=1;
}else if(sum==-d){
mask|=2;
}
}
//如果没有d或-d直接返回
if(mask==0){
return false;
}
//进行配对,所有的自己分为包含d或-d 或者不包含d或-d
List<Integer> S=new ArrayList<Integer>();
List<Integer> T=new ArrayList<Integer>();
//已经进行配对的元素
Queue<Integer> vis=new LinkedList<Integer>();
//进行配对映射
for (int sum : sums) {
if (!vis.isEmpty() && vis.peek() == sum) {
vis.poll();
continue;
}
//进行配对
S.add(sum);
T.add(sum+d);
vis.offer(sum+d);
}
//搜索
if((mask&1)==1){
//当前元素为d
ans.add(d);
int[] t=new int[S.size()];
for(int i=0;i<S.size();i++){
t[i]=S.get(i);
}
if(dfs(n-1,ans,t)){
return true;
}else{
ans.remove(ans.size()-1);
}
}
if(((mask>>1)&1)==1){
ans.add(-d);
int[] t=new int[T.size()];
for(int i=0;i<T.size();i++){
t[i]=T.get(i);
}
if(dfs(n-1,ans,t)){
return true;
}else{
ans.remove(ans.size()-1);
}
}
return false;
}
}
