Find minimum weight path in triangle: solution is incorrect

#1

The solution from the book is incorrect:

def minimum_path_weight(triangle):                                                
    min_weight_to_curr_row = [0]                                                  
    for row in triangle:                                                          
        min_weight_to_curr_row = [                                                
            row[j] +                                                              
            min(min_weight_to_curr_row[max(j - 1, 0)],                            
                min_weight_to_curr_row[min(j, len(min_weight_to_curr_row) - 1)])
            for j in range(len(row))                                              
        ]                                                                         
                                                                                  
        return min(min_weight_to_curr_row)

Also, maybe I understand it wrong but this claim seems wrong:

…consider entries at the ith row. For any such entry, if you look at the minimum weight path ending at it, the part that ends at the previous row must also be a minimum weight path.

If that were true, we could have a greedy algorithm that starts from the top and always chooses the next adjacent entry that is the smallest (I think that’s what the solution from the book is trying to do)

Here is a solution that passes all the tests:

def minimum_path_weight(triangle):                                             
                                                                               
    if not triangle:                                                           
        return 0                                                               
                                                                               
    for i in range(len(triangle) - 2, -1, -1):                                 
        for j in range(len(triangle[i])):                                      
            triangle[i][j] += min(triangle[i + 1][j], triangle[i + 1][j + 1])  
                                                                               
    return triangle[0][0]
0 Likes