需要帮助优化动态规划问题解决方案

Question

The problem statement:

Given two arrays a and b with sizes n and m respectively. All numbers in these arrays are in the range of 0 to 9 inclusive. Lets create a matrix with size of n x m where values in row i and column j is equal to ai * 10^9 + bj. Find the path from square 1,1 to n,m with the maxium sum. You're allowed to move forward or down.

Input parameters: The first line contains n and m (1 <= n, m <= 100 000)

The second line contains values of array a

The third line contains values of array b

Output Print the maximum sum

Time limit: 1 second

Memory limit: 512MB

示例：

输入：

7 4
0 7 1 7 6 7 6
4 1 9 7

输出：55000000068

我尝试用动态规划来解决这个问题，但是我的解决方案在O(n * m)有效并且无法通过时间限制：

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int main() {
        int n, m; cin >> n >> m;

        vector<uint64_t> a(n), b(m);
        for(int i = 0; i < n; i++) {
            int tmp;
             cin >> tmp;
             a[i] = tmp * 10e8;
        }

        for(int i = 0; i < m; i++) cin >> b[i];

        vector<uint64_t> dp(m);
        dp[0] = a[0] + b[0];

        for (int i = 1; i < m; i++)
            dp[i] = dp[i-1] + a[0] + b[i];

        for (int i = 1; i < n; ++i) {
            for(int j = 0; j < m; ++j) {
                if (j == 0)
                    dp[j] = dp[j] + a[i] + b[j];
                else
                    dp[j] = max(dp[j], dp[j-1]) + a[i] + b[j];
            }
        }

        cout << dp.back() << endl;

        return 0;
}

Answer 1

无需动态规划即可解决此问题，并且需要 O(n+m) 的内存和时间要求。

正如 @Botje 在评论中指出的那样，a 中更高价值的回报是非常大的。因此，最佳路径将保留在最左边的列中，直到它达到 a 中的最大值（在上例中为 7）。如果这个最大值在 a 中只出现一次，那么最好的选择是消耗整行，然后是所有后续行的最后一个元素，直到我们到达右下角角落.

但是，如果这个最大值出现不止一次，我们可以通过沿着第一行向右移动最大值 a 直到我们到达一列来获得更好的分数最大值为 b，然后将此列向下移动到包含最大值 a 的最后一行。然后我们可以像以前一样使用该行的其余部分，然后是所有后续行的最后一个元素。

也许插图会有所帮助：

    a = [ 0, 6, 9, 9, 0, 9, 3, 1 ]
    b = [ 1, 3, 2, 8, 4, 8, 1, 6 ]

   Col:  0     1     2     3     4     5     6     7
  Row:
   0    0,1   0,3   0,2   0,8   0,4   0,8   0,1   0,6 
         v
   1    6,1   6,3   6,2   6,8   6,4   6,8   6,1   6,6 
         v 
   2    9,1 > 9,3 > 9,2 > 9,8   9,4   9,8   9,1   9,6 
                           v
   3    9,1   9,3   9,2   9,8   9,4   9,8   9,1   9,6 
                           v
   4    0,1   0,3   0,2   0,8   0,4   0,8   0,1   0,6 
                           v
   5    9,1   9,3   9,2   9,8 > 9,4 > 9,8 > 9,1 > 9,6 
                                                   v
   6    3,1   3,3   3,2   3,8   3,4   3,8   3,1   3,6 
                                                   v
   7    1,1   1,3   1,2   1,8   1,4   1,8   1,1   1,6

本例中，a = 9的行共有三行，分别是第2、3、5行，为了得到最大的分数，我们需要按照第一个这些行（即第 2 行），直到我们到达最大值为 b 的列（无论是第 3 列还是第 5 列，都没有区别）。然后向下移动到最后一行a=9（第5行），向右移动到这一行的末尾，最后向下移动到右下角。

我已将此答案早期版本的 Python 代码转换为 C++。在数组 a 和 b 中使用 10⁵ 个随机值进行测试时，它产生的结果约为 0.3在我的系统上秒。上面的动态规划解决方案给出了相同的结果，但大约需要 4 分钟：

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

    vector<int64_t> a(n), b(m);
    int tmp, astart, aend, bmax, i, j;
    
    // Read in arrays a[] and b[]. At the same time,
    // find the first and last indices of the maximum
    // value in a[] (astart and aend) and any index
    // corresponding to the maximum value of b[] (bmax)
    
    for (tmp = -1, i = 0; i < n; i++) {
        cin >> a[i];
        if (a[i] >= tmp) {
            aend = i;
            if (a[i] > tmp) {
                astart = i;
                tmp = a[i];
            }
        }
        a[i] *= 1000000000LL;
    }
    for (tmp = -1, j = 0; j < m; j++) {
        cin >> b[j];
        if (b[j] > tmp) {
            tmp = b[j];
            bmax = j;
        }
    }
    
    // Trace through the matrix. First work down as far as
    // astart, then right until column bmax. Then work down
    // as far as row aend, add the remaining elements in this
    // row, and finally add the last element of each remaining
    // rows until we reach the bottom right corner.
    
    i = j = 0;
    int64_t tot = a[i] + b[j];
    while (i < astart) tot += a[++i] + b[j];
    while (j < bmax) tot += a[i] + b[++j];
    while (i < aend) tot += a[++i] + b[j];
    while (j < m-1) tot += a[i] + b[++j];
    while (i < n-1) tot += a[++i] + b[j];
        
    cout << tot << endl;
    return 0;
}

需要帮助优化动态规划问题解决方案

Need help to optimize dynamic programming problem solution

c++

algorithm

dynamic-programming