3

我被卡住的问题是，一个人需要从包含整数的二维数组的左上角到右下角的位置，获得最大可能的分数，无论是向下还是向右移动。但是，如果位置 A[i][j] 小于 0，则此人不能移动经过它，并且每次该人访问该位置的邻域时，都会从分数中减去等于该负值的数量. 我知道这是一个标准的 DP 问题，我可以制作一个数组 T[][]，其中 T[i][j] 表示从 0,0 到位置 i,j 的最大分数。但是，我无法提出任何适当的实现条件，即人不应该越过标有负整数的单元格。例如，如果行=2；列=3；和

A= | 0  -4   8 |
   | 1   1   0 |

那么我希望答案是 -6，即矩阵 T 应该是

 T=| 0  -4   X |
   | -3 -6  -6 |
  1. 鉴于在开始和结束位置，该人没有被“抢走”他的分数。
  2. X 表示该人无法到达相应的位置。在上述情况下，人不能越过 A[0][1] 去 A[0][2]
  3. T[row-1][column-1] 是问题的答案，即人从 A[0][0] 到 A[row-1][column-1] 可以获得的最高分
4

2 回答 2

1

我遵循与dwrd的答案中建议的相同思路，因此我尝试在 Python 中实现它。有一些事情需要考虑，我最初没有想到，但我想我终于让它工作了。

这是代码，它肯定需要一些修饰，但这是一个开始：

def get_score(M, i, j):
    "Get the final score for position [i, j.]"
    score = 0

    if M[i][j] < 0:
        score = -float('inf')
    else:
        score = M[i][j]
        score = score + penalty(M, i - 1, j - 1)
        score = score + penalty(M, i - 1, j + 1)
        score = score + penalty(M, i + 1, j - 1)
        score = score + penalty(M, i + 1, j + 1)
        score = score + penalty(M, i - 1, j)
        score = score + penalty(M, i, j - 1)
        score = score + penalty(M, i + 1, j)
        score = score + penalty(M, i, j + 1)

    return  score

def penalty(M, i, j):
    "Calculate the penalty for position [i, j] if any."
    if i >= 0 and i < len(M) and j >= 0 and j < len(M[0]):
        return (0 if M[i][j] > 0 else M[i][j])

    return 0

def calc_scores(M):
    "Calculate the scores matrix T."
    w = len(M[0])
    h = len(M)
    T = [[0 for _ in range(w)] for _ in range(h)]

    for i in range(h):
        for j in range(w):
            T[i][j] = get_score(M, i, j)

    T[0][0] = 0
    T[h - 1][w - 1] = 0

    return T

def calc_max_score(A, T):
    "Calculate max score."
    w = len(A[0])
    h = len(A)
    S = [[0 for _ in range(w + 1)] for _ in range(h + 1)]

    for i in range(1, h + 1):
        for j in range(1, w + 1):
            S[i][j] = max(S[i - 1][j], S[i][j - 1]) + T[i - 1][j - 1]

            # These are for the cases where the road-block
            # is in the frontier
            if A[i - 1][j - 2] < 0 and i == 1:
                S[i][j] = -float('inf')

            if A[i - 2][j - 1] < 0 and j == 1:
                S[i][j] = -float('inf')
    return S

def print_matrix(M):
    for r in M:
        print r

A = [[0, -4, 8], [1, 1, 0]]
T = calc_scores(A)
S = calc_max_score(A, T)

print '----------'
print_matrix(T)
print '----------'
print_matrix(S)
print '----------'

A = [[0, 1, 1], [4, -4, 8], [1, 1, 0]]
T = calc_scores(A)
S = calc_max_score(A, T)

print '----------'
print_matrix(T)
print '----------'
print_matrix(S)
print '----------'

您会得到以下输出：

----------
[0, -inf, 4]
[-3, -3, 0]
----------
[0, 0, 0, 0]
[0, 0, -inf, -inf]
[0, -3, -6, -6]
----------

----------
[0, -3, -3]
[0, -inf, 4]
[-3, -3, 0]
----------
[0, 0, 0, 0]
[0, 0, -3, -3]
[0, 0, -inf, 1]
[0, -3, -6, 1]
----------
于 2012-08-23T20:44:56.487 回答
1

这个想法是模拟无法移动到负无穷大结果的负单元格，该负无穷大结果永远不会被选为最大值。伪代码：

int negativePart(int i, int j)
{
    if (i < 0 || j < 0)
        return 0;
    return A[i, j] < 0 ? A[i, j] : 0;
}

int neighborInfluence(int i, int j)
{
    if (int == Height -1 && j == Width - 1)
        return 0;
    return negativePart(i-1, j-1) + negativePart(i-1,j)+// so on, do not think about negative indexes because it was already processed in negativePart method
}

int scoreOf(int i, int j)
{
    return A[i,j] < 0 ? <NegativeInfinity> : A[i,j] + neighborInfluence(i,j);
}

//.......

T[0,0] = A[0,0];
for (int i = 1; i < heigth; ++i)
{
    T[i, j] = T[i - 1, 0] + scoreOf(i, 0);
}

for (int i = 1; i < width; ++i)
{
    T[0, i] = T[0, i - 1] + scoreOf(0, i);
}

for (int i = 1; i < heigth; ++i)
{
    for (int j = 1; j < width; ++j)
    {
        T[i, j] = max(T[i - 1, j], T[i, j - 1]) + scoreOf(i, j);
    }
}
于 2012-08-23T19:30:31.743 回答