Meta旋转锁编程题（第二章）求助：仅通过2/32测试用例

这是Meta招聘页面的编程练习题，我目前的解决方案仅通过了2/32个测试用例，求能全通过的解法。

我的现有代码：

from typing import List
# Write any import statements here

def getMinCodeEntryTime(N: int, M: int, C: List[int]) -> int:
  # Write your code here
  dial_1 = 1
  dial_2 = 1
  count = 0
  code = C
  
  if len(code) > 0:
    for number in code:
      print("before: dial_1, dial_2: ", dial_1, dial_2)

      fwd_1 = abs(number - dial_1)
      rev_1 = N - abs(number - dial_1)

      fwd_2 = abs(number - dial_2)
      rev_2 = N - abs(number - dial_2)

      # Dial 1 calc: fwd vs rev
      if fwd_1 > rev_1:
        count_1 = rev_1
      else:
        count_1 = fwd_1

      # Dial 2 calc: fwd vs rev
      if fwd_2 > rev_2:
        count_2 = rev_2
      else:
        count_2 = fwd_2

      # Dial 1 vs Dial 2 movement decision
      if count_1 > count_2:
        dial_2 = number
        count += count_2
      else:
        dial_1 = number
        count += count_1

      print("after: dial_1, dial_2: ", dial_1, dial_2, "+/-", count)
    
  return count

现有代码问题分析 #

你的代码采用贪心思路，每次选当前两个拨盘到目标数字步数更少的那个移动，但局部最优的选择不一定能得到全局最优解——比如有时候选步数较多的拨盘移动，后续总步数反而会更小。因此需要用动态规划追踪所有可能状态，找到全局最小步数。

正确解法（动态规划） #

from typing import List

def getMinCodeEntryTime(N: int, M: int, C: List[int]) -> int:
    if M == 0:
        return 0
    
    # 计算两个数字间的最小移动步数（顺时针/逆时针取短路径）
    def min_steps(a, b):
        diff = abs(a - b)
        return min(diff, N - diff)
    
    # 初始状态：输入第一个数字后，一个拨盘在C[0]，另一个在初始位置1，记录总步数
    dp = {1: min_steps(1, C[0])}
    
    for i in range(1, M):
        current_num = C[i]
        prev_num = C[i-1]
        new_dp = {}
        # 遍历上一步所有可能的状态
        for other_pos, total in dp.items():
            # 情况1：移动之前在prev_num的拨盘到current_num
            cost = min_steps(prev_num, current_num)
            if other_pos in new_dp:
                new_dp[other_pos] = min(new_dp[other_pos], total + cost)
            else:
                new_dp[other_pos] = total + cost
            
            # 情况2：移动之前在other_pos的拨盘到current_num
            cost = min_steps(other_pos, current_num)
            if prev_num in new_dp:
                new_dp[prev_num] = min(new_dp[prev_num], total + cost)
            else:
                new_dp[prev_num] = total + cost
        dp = new_dp
    
    # 所有状态中的最小步数即为答案
    return min(dp.values())

解法说明 #

• 状态定义：用dp字典记录输入完前i个数字后，一个拨盘在当前数字C[i]、另一个拨盘在x位置的最小总步数。
• 状态转移：对每个新数字，有两种移动方式：要么移动上一个数字所在的拨盘到当前数字，要么移动另一个拨盘到当前数字。两种方式都计算总步数，保留每个状态的最小值。
• 空间优化：用字典存储状态，只保留上一步的所有可能状态，避免不必要的空间消耗。

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