需要帮助优化动态规划问题的解决方案
mak*_*bek 6 c++ algorithm dynamic-programming
问题陈述：
鉴于两个数组
a，并b用尺寸n和m分别。这些数组中的所有数字都在 0 到 9 的范围内。让我们创建一个矩阵，n x m其中行i和列中的j值等于ai * 10^9 + bj。找到从平方1,1到n,m最大和的路径。您可以向前或向下移动。输入参数：第一行包含
n和m(1 <= n, m <= 100 000)第二行包含数组的值
a第三行包含数组的值
b输出 打印最大和
时间限制：1秒
内存限制：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;
}
可以在没有动态规划的情况下解决这个问题，并且需要 O(n+m) 内存和时间要求。
正如指出的@Botje的意见，在奖励值越高一个是压倒性大。因此最佳路径将保留在最左边的列，直到它到达在最大值一（也就是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 5 个随机值的测试中，它在我的系统上大约 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;
}