求Bob作业完成安排问题的Dynamic Programming递推关系与解法

问题描述 #

Bob需完成编号1至N的N项作业，作业分属1至B门科目。要求：

• 必须按作业编号顺序分多天完成，每天至少完成1项
• 同一天内不能完成同一科目的多项作业
  求满足条件的完成方式总数，结果对1000000007取模。

给定数组A（A[i]为第i+1项作业的科目）和整数B，返回取模后的结果。

约束：1 ≤ N, B ≤ 100000，1 ≤ A[i] ≤ B

示例：

• 输入：A = [1,2,1,2,2], B=2 → 输出：5
• 输入：A = [1,2,3,4,5,6], B=6 → 输出：32

解法思路 #

采用动态规划结合记录科目上次出现位置的方法：

1. 状态定义：dp[i]表示完成前i项作业的合法方式总数（i从0到N，dp[0]=1为递推基础，代表空作业的虚拟方式）。
2. 辅助数组：last数组记录每个科目上一次出现的作业编号（1-based），初始化为0表示未出现过。
3. 状态转移：
   • 若当前科目从未出现过：每一种前i-1项的完成方式，都可选择将第i项单独开一天，或加入前一天（前一天无该科目），因此dp[i] = (dp[i-1] * 2) % MOD。
   • 若当前科目上一次出现的位置就是前一项（i-1）：前一天必然包含该科目，无法将第i项加入前一天，只能单独开一天，因此dp[i] = dp[i-1] % MOD。
   • 其他情况：先按无限制计算（dp[i-1]*2），再减去非法方式数——即把第i项与上一次同科目作业放在同一天的方式数，这部分数量等于dp[last[subject]-1]，因此dp[i] = (dp[i-1] * 2 - dp[last[subject]-1] + MOD) % MOD（加MOD避免负数）。

代码实现 #

MOD = 10**9 + 7

def count_homework_ways(A, B):
    n = len(A)
    dp = [0] * (n + 1)
    dp[0] = 1  # 递推基础：空作业的虚拟方式
    last = [0] * (B + 1)  # 记录每个科目上一次出现的作业编号（1-based）
    
    for i in range(1, n + 1):
        subject = A[i-1]
        prev_pos = last[subject]
        
        if prev_pos == 0:
            # 科目从未出现过，两种选择：单独开天或加入前一天
            dp[i] = (dp[i-1] * 2) % MOD
        elif prev_pos == i-1:
            # 上一项就是同科目，只能单独开天
            dp[i] = dp[i-1] % MOD
        else:
            # 减去非法方式：和上一次同科目作业在同一天的情况
            dp[i] = (dp[i-1] * 2 - dp[prev_pos - 1]) % MOD
            # 确保结果非负
            if dp[i] < 0:
                dp[i] += MOD
        
        # 更新当前科目最后出现的位置
        last[subject] = i
    
    return dp[n]

# 示例验证
print(count_homework_ways([1,2,1,2,2], 2))  # 输出5
print(count_homework_ways([1,2,3,4,5,6], 6))  # 输出32

示例解释 #

• 示例1：第5项作业科目为2，上一次出现位置是第4项，因此只能单独开天，方式数等于前4项的5种，最终输出5。
• 示例2：所有作业科目均不重复，每一步都有两种选择，最终方式数为2^(6-1)=32，符合输出。

内容的提问来源于stack exchange，提问作者Mohit Soni