04119: 复杂的整数划分问题

dp, http://cs101.openjudge.cn/practice/04119

将正整数n 表示成一系列正整数之和，n=n1+n2+…+nk, 其中n1>=n2>=…>=nk>=1 ，k>=1 。 正整数n 的这种表示称为正整数n 的划分。

输入

标准的输入包含若干组测试数据。每组测试数据是一行输入数据,包括两个整数N 和 K。 (0 < N <= 50, 0 < K <= N)

输出

对于每组测试数据，输出以下三行数据: 第一行: N划分成K个正整数之和的划分数目 第二行: N划分成若干个不同正整数之和的划分数目 第三行: N划分成若干个奇正整数之和的划分数目

样例输入

5 2

样例输出

2
3
3

提示

第一行: 4+1, 3+2, 第二行: 5，4+1，3+2 第三行: 5，1+1+3， 1+1+1+1+1+1

# https://blog.csdn.net/hejnhong/article/details/105211551
def divide_k(n, k):
    # dp[i][j]为将i划分为j个正整数的划分方法数量
    dp = [[0]*(k+1) for _ in range(n+1)]
    for i in range(n+1):
        dp[i][1] = 1
    for i in range(1, n+1):
        for j in range(1, k+1):
            if i >= j:
                # dp[i-1][j-1]为包含1的划分的数量
                # 若不包含1，我们对每个数-1仍为正整数，划分数量为dp[i-j][j]
                dp[i][j] = dp[i-j][j]+dp[i-1][j-1]
    return dp[n][k]


def divide_dif(n):
    # dp[i][j]表示将数字 i 划分，其中最大的数字不大于 j 的方法数量
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            # 比i大的数没用
            if i < j:
                dp[i][j] = dp[i][i]
            # 多了一种：不划分
            elif i == j:
                dp[i][j] = dp[i][j - 1] + 1
            # 用/不用j
            else:
                dp[i][j] = dp[i][j - 1] + dp[i - j][j - 1]
    return dp[n][n]


# 关于分拆数的一个结论，https://zhuanlan.zhihu.com/p/21440865
# 一个数的奇分拆总是等于互异分拆
def divide_odd(n):
    # dp[i][j]整数i的划分里最大的数是j
    dp = [[0] * (n + 1) for _ in range(n + 1)]
    dp[0][0] = 1
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if j % 2 == 0:
                dp[i][j] = dp[i][j-1]
            else:
                if i < j:
                    dp[i][j] = dp[i][i]
                elif i == j:
                    dp[i][j] = dp[i][j - 1] + 1
                # 用/不用j
                else:
                    dp[i][j] = dp[i][j - 1] + dp[i - j][j]

    return dp[n][n]


while True:
    try:
        n, k = map(int, input().split())
        print(divide_k(n, k))
        print(divide_dif(n))
        print(divide_odd(n))
    except EOFError:
        break

关于分拆数的一个结论，https://zhuanlan.zhihu.com/p/21440865

2020fall-cs101，李博海。OJ04117简单整数划分可以对应到完全背包，OJ04119复杂整数划分的不重复整数可以对应到01背包。当然背包问题求的最大值，而这里求的是“选取物品刚好为n的方法数”。

划分为不重复整数和奇数，既可以枚举整数或奇数做0-1背包。

把work2的注释放开，会超时。work2，work3计算值相等。

# ref: https://www.cnblogs.com/huashanqingzhu/p/7300766.html
#   https://blog.csdn.net/qq_35479641/article/details/51951595

while True:
    try:
# N划分成K个正整数之和
# 设dp[n][k]表示数n划分成k个正整数之和时的划分数。 
#   划分分两种情况：

#   划分中不包含1：则要求每个数都大于1，可以先拿出k个1分到每一份，之后在n-k中再划分k份，即dp[n-k][k]。
#   划分中包含1：则从n中减去1，然后从n-1中再划分k-1份, 则划分数为dp[n-1][k-1]。
# 动态转移方程：dp[n][k]=dp[n-k][k]+dp[n-1][k-1]。        
        N,K = map(int, input().split())
        dp = [[0]*(K+1) for i in range(N+1)]
        for i in range(0, N+1):     #将i分成1个数只有一种方案
            dp[i][1] = 1
        
        for i in range(1, N+1):
            for j in range(2, K+1):
                if j <= i:
                    dp[i][j] = dp[i-1][j-1] + dp[i-j][j]
                    
        print(dp[N][K])

# N划分成若干个不同正整数之和
# 划分分两种情况：
#   划分中每个数都小于m：则划分数为dp[n][m-1]。
#   划分中至少有一个数等于m：则从n中减去m，然后从n-m中再划分，且再划分的数中每个数要小于m, 则划分数为dp[n-m][m-1]。
# 动态转移方程：dp[n][m]=dp[n][m-1]+dp[n-m][m-1]。

        """
        #work2
        dp2 = [[0]*(N+1) for i in range(N+1)]
        dp2[0] = [1 for j in range(N+1)]
        
        for i in range(N+1):
            for j in range(1,N+1):
                if j <= i:
                    dp2[i][j] = dp2[i][j-1] + dp2[i-j][j-1]
                else:
                    dp2[i][j] = dp2[i][i]
                    
        print(dp2[N][N])
        """

# N划分成若干个奇正整数之和的划分数目
        dp3 = [[0]*(N+1) for i in range(N+1)]
        for i in range(0, N+1):
            dp3[i][1] = 1           #将i分成1个数只有一种方案
            if i&1:
                dp3[0][i] = 1       #预处理第0层
        
        for i in range(1, N+1):
            for j in range(2, N+1):
                if j & 1 :
                    if j <= i:
                        dp3[i][j] = dp3[i-j][j] + dp3[i][j-1]
                    else:
                        dp3[i][j] = dp3[i][i]
                else:   #当前非奇数
                    dp3[i][j] = dp3[i][j-1]

        print(dp3[N][N])
        print(dp3[N][N])
        
    except EOFError:
        break