Understanding the difference between the two solutions to dfs and memoization

Question

I am looking forward to understand how one of these solutions works, but one doesn't. I am building the solution for the following problem :

two-city-scheduling

A company is planning to interview 2n people. Given the array 
costs where costs[i] = [aCosti, bCosti], the cost of flying the 
ith person to city a is aCosti, and the cost of flying the ith 
person to city b is bCosti.Return the minimum cost to fly every 
person to a city such that exactly n people arrive in each city.

The solution 1: that works

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)

In the solution 2 I am only trying to pass the cost as a parameter and calculate acordingly

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)

Here is the diff of the two solutions

However while both the solutions passes for the test : [[10,20],[30,200],[400,50],[30,20]] and [[515,563],[451,713],[537,709],[343,819],[855,779],[457,60],[650,359],[631,42]]

the 2nd one fails for the test case [[259,770],[448,54],[926,667],[184,139],[840,118],[577,469]]

I am trying to understand how is the second solution different from the 1st ! can anyone explain ?

Answer 1

Let's first reiterate what both algorithms have in common and what they intend to achieve:

Both algorithms intend to use a DP table to avoid recalculating the same subproblem twice. For a given city population after distribution of the first k persons, the calculation of the minimal cost from that state onwards is stored in that DP table. This way we hope to avoid a recalculation if we ever arrive in a similar state (with the same populations for the city after assigning the first k persons.

So for instance, let's say we have 6 persons. Let's say that after a while we arrive at a state where the first three persons are distributed such that the population in city A is 2 and the population in city B is 1 (the sum obviously has to be 3). This configuration is thus identified as (2, 1).

Both algorithms will then use recursion to come back with the cost for assigning one more person to A and 2 more to B (to arrive at a 3-3 distribution). They then select the least of the costs found to determine what to store for the configuration (2, 1).

The difference:

The first (correct) algorithm will store the minimal additional cost that is has still to be made.

The second (incorrect) algorithm will store the total cost that is made to achieve a valid distribution.

The problem

In the example, when the algorithms unwind recursion and create a different state that also has a (2, 1) configuration (so this time with a different person assigned to city B than the previous time), the problem becomes apparent:

Both algorithms will use the value stored in the DP table for that configuration (2, 1) and not continue assignments to reach the full 3-3 distribution. The correct algorithm can rightly say that the minimal remaining cost is exactly what is read from the DP table, but the incorrect algorithm cannot rightly say that the total cost found there is also the minimal total cost. The fact that we now have a different choice for the first 3 persons, means that we cannot make assumptions about the minimal total cost. It might be that we made less costs to reach this (2, 1) configuration than last time we were in this configuration, and so the minimum total cost we find in the DP table is not really the minimum. As the first three selections happened to be cheaper, this means the total cost should also be cheaper. And that is where the DP breaks down: it doesn't help us in the second algorithm.