c++ - 我需要一些关于动态规划的建议
问题描述
这就是问题所在:HaNa 是一个数学制造者。最初,他有一个数字 n。每次他执行一个动作,他都会移除任何元素x,使得x > 1,然后依次插入相同的位置3个数字:floor(x/2), x mod 2, floor(x/2)。他必须继续这个操作,直到他收到充满 0 和 1 的列表。
鉴于此,列表是 1 索引的(列表的第一个索引是 1)。实现一个函数 sumOfOnes 来计算列表中 l 和 r 范围内数字 1 的个数之和。
注意:
时间限制为 2 秒
0 <=n< 2^50
0 <= rl <= 10^5
r >= l
l >= 1
我使用bottom_up 方法(动态编程)来解决这个问题 int limit time。这是我的代码:
string hana(long long int n)
{
string* memoize = new string[n+1];
memoize[0] = "0";
memoize[1] = "1";
for(long long int i = 2; i <= n; ++i)
{
if(i%2 == 0) memoize[i] = memoize[i/2] + "0" + memoize[i/2];
else memoize[i] = memoize[i/2] + "1" + memoize[i/2];
}
return memoize[n];
}
//
long long int sumOfOnes (long long int n, long long int l, long long int r){
string result = hana(n);
long long int ans = 0;
for(long long int i = l - 1; i <= r - 1; ++i)
{
if(result[i] == '1') ++ans;
}
return ans;
}
它适用于小输入,但由于内存不足,它不适用于大输入!我真的需要一些关于如何处理大量输入的建议。非常感谢!!!
解决方案
首先,除了几个设计缺陷之外,您还有一个严重的内存泄漏问题,因为您在没有正确删除的情况下堆分配了一个本地数组。
string* memoize = new string[n+1];
不要以这种方式在本地执行此操作,请为此使用 std::vector :
auto memoize = std::vector<std::string>(n + 1);
此外,您正在为每个实际值请求一次又一次地重新创建数组。至少对于您当前使用完全初始化数组的求解方案,应该避免这种情况,使用 hana-array 的更“全局”存储位置(预先分配最大可能的 N)!
对于您的实际算法问题,这里没有更深入的数学洞察力,并且感觉原始问题的陈述更详细/更精确......:
您将永远无法以可接受的方式在 n 大约 50 的当前方法中解决此问题。
关键是:这是一个常见的对数问题类,例如二进制搜索。您应该尝试重新设计对递归函数调用访问的数组访问,因此对第 n 个元素的访问始终通过函数调用完成,并且只有前两个元素实际上是“具体的”。如果首先在这里没有更深入的分析,复杂性应该已经可以降低到 O(log(n) * (r - l)) 左右。我会尝试向您发布解决方案,但请首先确保您在此处提供了完整的问题描述!
推荐阅读
- csv - 如何在 CSV 文件的一列中分隔两个值?
- mysql - 在内部连接Mysql中查找最近的时间
- powershell - PowerShell PipelineVariable 参数仅包含 PSCustomObject 集合中的第一个值
- arrays - 投票生成器阵列和循环仅
- swift - 为什么 O(n) 比 O(n^2) 花费更长的时间?
- python - Windows 中 OpenCV imshow 中的缩放功能
- yii2 - Yii2 kartik 依赖下拉列表不加载下一个下拉列表
- r - 从非因子列生成键列
- python - 在 Firestore 中的集合内迭代集合
- mpich - 无法在 Ubuntu 14.04 上使用新安装的 MPICH mpich-3.2.1