最大和寻路动态规划求解

Question

问题是我有一个由数字填充的 2 * n 数组。我想从 (0,0) 单元格开始向右、向上或向下移动以到达 (1,n) 单元格。每个单元最多应该被访问一次，并且路径中的数字总和应该是最大的。例如，如果我有这个数组：

1 2 5
-1 3 4

动作应该是下、右、上、右、下。所以最大和是 1 + (-1) + 3 + 2 + 5 + 4 = 14

我试图通过找到每列的最大元素来使用动态规划来解决问题，但这没有用。我的解决方案是这样的：

dp[0][0] = arr[0][0];
dp[1][0] = arr[1][0] + arr[0][0];
for (int i = 1; i < n; i++) {
    // here we predict 4 numbers and find the maximum one
    // so we can get maximum score on each column
    int predicta1 = arr[1][i] + dp[1][i - 1]; // predict for 1,i (down)
    int predicta2 = predicta1 + arr[0][i];    // predict for 0,i (up)

    int predictb1 = arr[1][i] + arr[0][i] + dp[0][i - 1]; // predict for 1,i (down)
    int predictb2 = arr[0][i] + dp[0][i - 1]; // predict for 0,i (up)
    int maximum = max(predicta1, max(predicta2, max(predictb1, predictb2)));
}

任何人都可以帮助如何使用 DP 或任何其他方法解决此问题？

Answer 1

您离解决方案不远了。这个想法是利用我们不能向左走的事实。

我们迭代计算位置 [0][i] 和 [1][i] 处的最大值。例如：

Max at [1][i] = max (Max at [1][i-1] + A[1][i], Max at [0][i-1] + A[0][i] + A[1][i]);

等等

#include <iostream>
#include <vector>
#include <algorithm>

int path2 (std::vector<std::vector<int>>& A) {
    int n = A[0].size();
    if (n == 0) return 0;
    int predit0 = A[0][0];
    int predit1 = A[0][0] + A[1][0];
    
    for (int i = 1; i < n; ++i) {
        int sum = A[0][i] + A[1][i];
        int temp = std::max (predit0 + A[0][i], predit1 + sum);
        predit1 = std::max (predit1 + A[1][i], predit0 + sum);
        predit0 = temp;
    }
    return predit1;
}

int main() {
    std::vector<std::vector<int>> A = {
        {1, 2, 5},
        {-1, 3, 4}
    };
    auto ans = path2(A);
    std::cout << "max sum = " << ans << std::endl;
    return 0;
}

最大和寻路动态规划求解

dynamic programming solution on path finding with maximum sum

algorithm

dynamic-programming