算法作业-求解数字和为sum的方法数问题（dp）
发布时间
阅读量：
阅读量
鉴于n的数量级超过1000，显然无法采用穷举的方式进行处理，因此只能借助动态规划的方法来实现问题的求解。在实际操作过程中，我选择使用一个映射结构来进行数据的存储与查找，相较于数组而言，这种方式能够在一定程度上减少内存的占用。具体来说，每一列的数值会与前一列的数据相加，其中映射结构的第一个元素用于存储数值本身，第二个元素则用于记录该数值出现的次数。当数值等于目标值sum时，可以直接进行统计操作，而无需继续累加至后续列中。
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::map;
int main()
{
int n, sum, a;
vector<map<int, int>>dp;全部评论 (0)
还没有任何评论哟~