Find path in grid with mostly k moves and maximum score
I am trying to solve the following problem: given an N by M grid of positive integers, find a maximum score you can get by traveling from the top left corner to the bottom right one. A score of a path is the sum of all the values you collect on the said path (staying on the same cell is a possible turn). Also, the length of the path must be mostly L . For example: let's say we have the following grid ( N = 5 , M = 6 ):
1 1 1 1 1 1
10 10 1 1 1 1
1 10 1 10 10 10
1 10 10 10 1 10
1 1 1 1 1 1
If L = 10 , the answer should be 83. You get this by following this path:
1
10 10
10
10 10 10 1 10
1
And staying on one of the 10's for a single turn.
If L = 11 , the answer should be 102. You get this by following the path of 10's in the original grid.
I have come up with an algorithm of complexity O(N^2*M^2*L), but this is too slow, as N and M can go up to 100 and L can go to 1000. My algorithm's basic idea is as follows: calculate the answer for each tuple (i1, j1, i2, j2, k) , where (i1, j1) is the starting cell, (i2, j2) is the destination cell and k is the path length. I start from k = 0 and work my way up to L . Do you have any suggestions on how I could optimize this idea? Or even a whole new insight into the problem?
One possible approach is to compute for each tuple of the form (i, j, k), the maximum score of a path of length exactly k, that starts from cell (0, 0), and ends in (i, j). Let us denote this value as best(i, j, k).
By convention, if there is no path of length k starting in (0, 0) and ending in (i, j), we want to have best(i, j, k) = -infinity.
For k = 1, there is a single path with length 1 that starts in the top-left corner, therefore:
For k > 1 we can compute best(i, j, k) using the values of best(*, *, k - 1):
best(i, j, k) = input_matrix(i, j) + max(best(a, b, k - 1)), where the max is taken over all a, b, such that the cell (a, b) is a neighbor of the cell (i, j).
Now, that the best matrix has been constructed, the answer to the original question can be found by computing:
max(best(N - 1, M - 1, k)), where the max is taken over all k between 1 and L.
The complexity of this approach is O (N ⋅ M ⋅ L).
链接地址: http://www.djcxy.com/p/63854.html上一篇: Emacs设置哪个