855学习记录算法动态规划$Day$-$4$——炎泽汐$de$ Blog

多重部分和问题

---

//多重部分和问题
int MultipartSum(int a[], int m[], int n, int k){
    int dp[n + 1];
    memset(dp, -1, sizeof(dp));
    dp[0] = 0;
    for(int i = 0; i <= n; i++){
        for(int j = 0; j <= k; j++){
            if(dp[j] >= 0){
                dp[j] = m[i];
            }else if(j < a[i] || dp[j - a[i]] <= 0){
                dp[j] = -1;
            }else{
                dp[j] = dp[j - a[i]] - 1;
            }
        }
    }
    return dp[k];
}

划分数

---

//划分数
int PartitionNumber(int n, int m, int M){
    int dp[n + 1][m + 1];
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
    for(int i = 0; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(i - j >= 0){
                dp[i][j] = dp[i - j][j] + dp[i][j - 1];
            }else{
                dp[i][j] = dp[i][j - 1];
            }
        }
    }
    return dp[n][m];
}

      进一步，如果要求每个集合的数量大于一：

//正整数划分数
int PartitionNumber(int n, int m, int M){
    int dp[n + 1][m + 1];
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(i - j >= 0){
                dp[i][j] = dp[i - j][j] + dp[i - 1][j - 1];
            }else{
                dp[i][j] = dp[i - 1][j - 1];
            }
        }
    }
    return dp[n][m];
}

      更进一步，如果要求每个集合的数量大于一且互异：

//互异划分数
int DistinctivePartitionNumber(int n, int m, int M){
    int dp[m + 1][n + 1];
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(i - j >= 0){
                dp[i][j] = dp[i - j][j] + dp[i - j][j - 1];
            }
        }
    }
    return dp[n][m];
}

多重集组合数问题

---

      详见：

//多重集组合数问题
int MultipleSetCombinationNumber(int n, int m, int M, int a[]){
    int dp[m + 1][n + 1];
    memset(dp, 0, sizeof(dp));
    for(int i = 0; i <= n; i++){
        dp[i][0] = 1;
    }
	
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(j - 1 - a[i - 1] >= 0){
            	//避免负数  
                dp[i][j] = (dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1 - a[i - 1]] + M) % M;
            }else{
                dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % M;
            }
        }
    }
	return dp[n][m];
}