沿河流动工匠营收最大化的dynamic programming伪代码咨询

核心逻辑梳理 #

思路卡壳的核心原因是漏了两个关键状态维度，没有把「permit审批进度」和「移动动作的原子性」纳入DP定义：

• 移动是固定耗时2天的原子动作，不需要拆分到2天里逐天决策，选了移动就直接跳转到2天后的相邻城镇节点
• permit等待是落脚到新城镇后才开始计算的流程，移动赶路的时间不算在等待周期里；离开当前城镇后再返回，需要重新走一遍permit审批流程
• 必须把「permit已获批可自由选择」和「仍在等待审批」的场景分开建模，否则会出现未到等待时间就提前拿收入的逻辑错误

状态定义 #

基于逆序推导的逻辑，从最后一天往第1天计算，定义两个DP表：

• dp_work[t][i]：第t天位于城镇i，且该城镇permit已完成审批、可自由决策工作/离开时，从第t天到最后一天能拿到的最大总营收
• dp_wait[t][i][w]：第t天刚抵达城镇i，还需要等待w天审批才能开工时，从第t天到最后一天能拿到的最大总营收

全局常量对齐题目规则：

• T为总可工作天数，即len(revenue)
• 城镇1仅可移动到城镇2，城镇n仅可移动到城镇n-1，其余城镇可移动到左右相邻城镇
• 移动动作耗时2天，抵达新城镇后按该城镇的permit要求重新计算等待时间
• 起始状态：第1天在base城镇，无需等待permit，直接处于可工作状态

递推逻辑 #

边界条件 #

从最后一天（t=T）开始初始化：

• dp_work[T][i] = revenue[T][i]：最后一天permit已获批，可选动作只有当天在i工作，选择移动的话会超出时间范围拿不到收入
• dp_wait[T][i][w] = 0：最后一天无论还需要等多久审批，都来不及开工，移动也超时间，收益为0

转移方程 #

从t=T-1逆序计算到t=1，逐天更新两个DP表的值：

1. 更新dp_work[t][i]（当前已获批）：
   • 选择当天留下工作：收益为当日收入 + 次日仍在i的可工作状态收益
   • 选择移动到相邻城镇：收益为2天后抵达相邻城镇的对应状态收益（若抵达时间超出总天数则收益为0）
   • dp_work[t][i]取两类选择的最大值
2. 更新dp_wait[t][i][w]（当前仍在等审批）：
   • 选择继续等待1天：等待完成度向前推1格，若剩余等待时间为0则切换为可工作状态，否则保持等待状态
   • 选择放弃等待、直接移动到相邻城镇：收益计算和上述移动逻辑完全一致（移动动作不需要等permit审批完成）
   • dp_wait[t][i][w]取两类选择的最大值

伪代码实现 #

# 输入对齐：revenue为T个日期的收入列表，permit为n个城镇的审批天数列表，base为起始城镇编号
T = len(revenue)
n = len(permit)
max_p = max(permit) if permit else 0

# 初始化DP表，多开2行处理t+2超出总时间的边界情况，初始值为0
dp_work = 2D array of size (T + 3) x (n + 2), all 0
dp_wait = 3D array of size (T + 3) x (n + 2) x (max_p + 2), all 0

# 逆序从最后一天往前算
for t in range(T, 0, -1):
    # 计算每个城镇的可工作状态值
    for i in range(1, n+1):
        # 选项1：当天在i工作
        choose_work = revenue[t-1][i-1] + dp_work[t+1][i]
        # 选项2：从i移动到相邻城镇
        choose_move = 0
        neighbors = []
        if i == 1:
            neighbors = [2]
        elif i == n:
            neighbors = [n-1]
        else:
            neighbors = [i-1, i+1]
        for j in neighbors:
            if t + 2 > T:
                gain = 0
            else:
                # 刚到j，按permit要求算等待时间
                if permit[j-1] == 0:
                    gain = dp_work[t+2][j]
                else:
                    gain = dp_wait[t+2][j][permit[j-1]]
            choose_move = max(choose_move, gain)
        dp_work[t][i] = max(choose_work, choose_move)
    
    # 计算每个城镇不同等待天数的状态值
    for i in range(1, n+1):
        for w in range(1, max_p +1):
            # 选项1：继续等待1天
            if w -1 == 0:
                wait_gain = dp_work[t+1][i]
            else:
                wait_gain = dp_wait[t+1][i][w-1]
            # 选项2：直接出发移动到相邻城镇
            move_gain = 0
            neighbors = []
            if i ==1:
                neighbors = [2]
            elif i ==n:
                neighbors = [n-1]
            else:
                neighbors = [i-1, i+1]
            for j in neighbors:
                if t +2 > T:
                    gain =0
                else:
                    if permit[j-1] ==0:
                        gain = dp_work[t+2][j]
                    else:
                        gain = dp_wait[t+2][j][permit[j-1]]
                move_gain = max(move_gain, gain)
            dp_wait[t][i][w] = max(wait_gain, move_gain)

# 最终结果：第1天在base城镇，直接处于可工作状态
max_revenue = dp_work[1][base]

复杂度说明 #

• 时间复杂度：O(T * n * max_p)，逐天遍历所有城镇，每个城镇最多遍历max_p种等待状态，相邻城镇最多2个，整体计算量线性可控
• 空间复杂度：基础实现为O(T * n * max_p)，可通过滚动数组优化为O(n * max_p)（计算t天状态时仅需t+1和t+2天的结果，不需要保留所有历史天数的DP值）

规则校验：该实现完全覆盖题目要求的所有约束——离开城镇再返回时会自动触发重新等permit的逻辑，连续多日在同一城镇工作的选择会被自动纳入收益计算，移动耗时的规则完全对齐2天跨城的要求。

内容的提问来源于stack exchange，提问作者Sabine Telster