动态规划问题排查：最少不吃冰淇淋天数求解代码错误

Ram计划在N天内吃冰淇淋，每天冰淇淋店的口味用以下数值表示：

• 1：巧克力
• 2：芒果
• 3：两种口味都有
• 0：无口味

Ram不想连续两天吃同一种口味，需要计算Ram最少不吃冰淇淋的天数。

边界条件：1 ≤ N ≤ 100000
输入格式：第一行输入N，第二行输入N个整数；
输出格式：输出最少不吃冰淇淋的天数。

作为动态规划新手，我写的Python代码在测试用例中全部失败。其中一个隐藏用例是3001天的序列，预期输出1114，但我的代码输出1126，5个隐藏测试用例全挂，找不到错误原因，求帮忙排查。

n=int(input())
ar=list(map(int, input().split()))
dp=n*[-1]
c=0
prev, dp[0]=ar[0],ar[0]
for i in range(1,n-1):
    if ar[i]==prev:
        dp[i]=0
        prev=dp[i]
        continue
    if ar[i]==0:
        dp[i]=0
        prev=0
        continue
    if ar[i]==3 and prev==0:
        if ar[i+1]==1:
           dp[i]=2
        elif ar[i+1]==2:
           dp[i]=1
        prev=dp[i]
        continue
    if ar[i]==3 and prev==1:
        dp[i]=2
        prev=dp[i]
    elif ar[i]==3 and prev==2:
        dp[i]=1
        prev=dp[i]
    else:
        dp[i]=ar[i]
        prev=dp[i]
if prev==ar[n-1]:
    dp[n-1]=0
else:
    dp[n-1]=ar[n-1]
for i in dp:
    if i==0:
        c+=1
print(c)

你的代码存在几个核心问题：

1. 循环范围错误：range(1,n-1)会跳过倒数第二天，导致该天状态未被正确处理，最后处理最后一天时依赖的prev是倒数第三天的状态，逻辑完全错误，应改为range(1, n)遍历所有后续天数。
2. 贪心逻辑缺陷：处理ar[i]==3且prev==0时，仅通过下一天口味做选择是短视的，可能导致后续更多天数被迫选0，反而增加不吃的天数。动态规划需要跟踪全局最优，而非当前局部最优。
3. DP数组设计错误：你的dp仅记录当天选的口味，未记录到当前天为止的最少不吃天数，无法实现全局最优决策。

修正后的代码 #

n = int(input())
ar = list(map(int, input().split()))
if n == 0:
    print(0)
    exit()

# 用滚动数组优化空间，仅保存前一天的三种状态：选0、选1、选2的最少不吃天数
prev_dp = [0] * 3

# 初始化第一天状态
if ar[0] == 0:
    prev_dp[0] = 1
    prev_dp[1] = float('inf')
    prev_dp[2] = float('inf')
elif ar[0] == 1:
    prev_dp[0] = 1
    prev_dp[1] = 0
    prev_dp[2] = float('inf')
elif ar[0] == 2:
    prev_dp[0] = 1
    prev_dp[1] = float('inf')
    prev_dp[2] = 0
else:  # ar[0] ==3
    prev_dp[0] = 1
    prev_dp[1] = 0
    prev_dp[2] = 0

for i in range(1, n):
    curr_dp = [float('inf')] * 3
    curr_flavor = ar[i]
    # 当前天选0：不管前一天选什么，不吃天数+1
    curr_dp[0] = min(prev_dp) + 1
    # 当前天选1：仅当允许选1（1或3），且前一天没选1
    if curr_flavor in (1, 3):
        curr_dp[1] = min(prev_dp[0], prev_dp[2])
    # 当前天选2：仅当允许选2（2或3），且前一天没选2
    if curr_flavor in (2, 3):
        curr_dp[2] = min(prev_dp[0], prev_dp[1])
    prev_dp = curr_dp

# 取三种状态的最小值，即为最少不吃天数
print(min(prev_dp))

代码说明 #

• 滚动数组优化：仅保存前一天的状态，避免因N=1e5导致的内存溢出问题。
• 状态跟踪：每天记录选0、1、2三种情况下的最少不吃天数，每一步基于前一天的最优状态做决策，保证全局最优。
• 灵活处理3：遇到3时同时计算选1和选2的最优情况，不会因贪心选择导致后续损失。

内容的提问来源于stack exchange，提问作者Srinivasan A