I don't know how to approach this question.

We're given an N*N grid listing the costs to get from location a to location b.

Each row in the grid tells us the cost of getting from location to location (each location corresponds to a row in the costs array). (We say that location a is bigger than location b if row a appears after row b in the costs array. The index of every row is a location). We may choose to start from any given location, and visit every location exactly once. At every location p that we visit, we must have already visited all locations less than p, or no locations less than p.

• costs[a][b] gives us the cost to move from location a to location b.
• costs[a][b] is not necessarily the same as costs[b][a].
• costs[a][a] = 0 for every index a (diagonals in the costs array are always 0).

Our task is to find the maximum-sum cost of a valid path.

If the costs array is:

[[0, 9, 1],
 [5, 0, 2],
 [4, 6, 0]]

The max cost consequently will be 13 as the most expensive valid path is starting at location 2 -> location 0 -> location 1.

The first row tells us how much it will cost to get from location 0 to location 0 (remain in the same location, costs us 0), 0 to location 1 (costs us 9) and 0 to location 2 (costs us 1). The second and third rows follow the same pattern.

CodePudding user response：

The requirements on which locations you can visit mean that after you start at some location i, you're forced to move to a lower location repeatedly until you're at location 0. At that point, you have to ascend consecutively through all the locations that are unvisited. The dynamic programming solution is not obvious, but with a fairly complex implementation you can get an O(n^3) DP algorithm with standard techniques.

It turns out there's an O(n^2) solution as well, which is optimal. It also uses O(n) extra space, which is maybe also optimal. The solution comes from thinking about the structure of our visits: there's a downward sequence of indices (possibly with gaps) ending at 0, and then an upward sequence starting at 0 that contains all other indices. There's 2^n possible subsequences though, so we'll have to think more to speed this up.

Two Sequences

Suppose we have i locations, 0, 1, ... i-1, and we've partitioned these into two ordered subsequences (except 0, which is at the start of both). We'll call these two sequences U and D, for up and down. Exactly one of them has to end on i-1. Without loss of generality, assume U ends with i-1 and D ends with j >= 0.

What happens when we add a location i? We either add it to the end of U so our sequences end on i and j, or we add it to the end of D so our sequences end on i-1 and i. If we add it to U, the path-sum of U (which we define as the sum of cost[u][v] for all adjacent indices u,v in U) increases by cost[i-1][i]. If we add the location to the end of D, the path-sum of D increases by cost[i][j] (since it's a downward sequence, we've flipped the indices relative to U).

It turns out that we only need to track the endpoints of our subsequences as we grow them, as well as the maximum combined path-sum for any pair of subsequences with those endpoints. If we let (i, j) denote the state where U ends with i and D ends with j, we can think about how we could have arrived here.

For example, at (8,5), our previous state must have had a subsequence containing 7, so our previous state must have been (7,5). Therefore max-value(8,5) = max-value(7,5) cost[7][8]. We always have exactly one predecessor state when the two endpoints differ by more than one.

Now consider the state (8,7). We can't have come from (7,7), since the only number allowed to be in both sequences is 0. So we could have come from any of (0,7), (1,7), ... (6,7): we can choose whichever will maximize our path sum.

def solve(costs: List[List[int]]) -> int:
    n = len(costs)
    # Deal with edge cases
    if n == 1:
        return 0
    if n == 2:
        return max(costs[0][1], costs[1][0])

    ups = [costs[0][1]]
    downs = [costs[1][0]]

    # After iteration i, ups[j] denotes the max-value of state (i, j)
    # and downs[j] denotes the max-value of state (j, i)
    for i in range(2, n):
        ups.append(max(downs[j]   costs[j][i] for j in range(i - 1)))
        downs.append(max(ups[j]   costs[i][j] for j in range(i - 1)))

        up_gain   = costs[i-1][i]
        down_gain = costs[i][i-1]

        for j in range(i - 1):
            ups[j]    = up_gain
            downs[j]  = down_gain

    return max(max(ups), max(downs))