两城调度问题：两种DFS记忆化解法为何一解失效？

问题描述 #

一家公司计划面试2n人，给定costs数组，其中costs[i] = [aCosti, bCosti]，代表第i人飞往A城费用为aCosti，飞往B城费用为bCosti，需返回让每城恰好n人的最小总成本。

解法1（正确实现） #

import sys

class Solution(object):
    def twoCitySchedCost(self, costs):
        """
        :type costs: List[List[int]]
        :rtype: int
        """

        dp = {}

        def dfs(person, city_a_population, city_b_population):
            if((city_a_population, city_b_population) in dp):
                return dp[(city_a_population, city_b_population)]
            
            if (person > len(costs) -1):
                return 0

            result_a = sys.maxsize
            result_b = sys.maxsize

            if(city_a_population < len(costs)/2):
                result_a =  costs[person][0] + dfs(person + 1, city_a_population + 1, city_b_population)

            if(city_b_population < len(costs)/2):
                result_b =  costs[person][1] + dfs(person + 1, city_a_population, city_b_population + 1)

            dp[(city_a_population, city_b_population)] = min(result_a, result_b)

            return dp[(city_a_population, city_b_population)]

        
        return dfs(0, 0, 0)

解法2（存在bug的实现） #

import sys

class Solution(object):
    def twoCitySchedCost(self, costs):
        """
        :type costs: List[List[int]]
        :rtype: int
        """

        dp = {}

        def dfs(person, city_a_population, city_b_population, cost):
            if((city_a_population, city_b_population) in dp):
                return dp[(city_a_population, city_b_population)]
            
            if (person > len(costs) -1):
                return cost

            result_a = sys.maxsize
            result_b = sys.maxsize

            if(city_a_population < len(costs)/2):
                result_a =  dfs(person + 1, city_a_population + 1, city_b_population, costs[person][0] + cost)

            if(city_b_population < len(costs)/2):
                result_b =  dfs(person + 1, city_a_population, city_b_population + 1, costs[person][1] + cost)

            dp[(city_a_population, city_b_population)] = min(result_a, result_b)

            return dp[(city_a_population, city_b_population)]

        
        return dfs(0, 0, 0, 0)

测试情况 #

• 两个解法均通过测试用例：[[10,20],[30,200],[400,50],[30,20]] 和 [[515,563],[451,713],[537,709],[343,819],[855,779],[457,60],[650,359],[631,42]]
• 解法2在测试用例 [[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]] 中失败

核心差异与解法2失效原因 #

核心差异 #

两种解法的核心区别在于状态定义和记忆化存储的逻辑：

1. 解法1中，dp[(a, b)] 存储的是从当前person开始，已选a人去A城、b人去B城的情况下，完成剩余选择所需的最小成本。递归返回后续最小成本，当前成本在递归调用时累加。
2. 解法2中，dp[(a, b)] 试图存储从初始状态到当前(a,b)状态的累计总成本加上后续最小成本，但递归函数把累计成本cost作为参数传递，导致记忆化逻辑错误。

解法2失效的根本原因 #

解法2的记忆化存储键(city_a_population, city_b_population)无法唯一标识递归状态：

• 到达同一个(a,b)状态时，可能通过不同路径，累计的cost值不同。但解法2直接将第一次计算的结果存入dp，后续遇到相同(a,b)时直接复用该值，忽略了当前累计cost的差异。
• 比如在失败的测试用例中，不同路径到达同一个(a,b)状态时，累计cost不同，但解法2的记忆化会复用之前存储的非最优结果，最终导致计算出的总成本不是最小值。

而解法1中，dp[(a,b)]存储的是后续的最小成本，与之前的累计成本无关，无论通过什么路径到达(a,b)，后续的最小成本都是固定的，记忆化逻辑完全正确。

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