有序硬币组合的递归解II (CSES)

Question

问题链接

考虑一个由n个硬币组成的货币系统。每个硬币都有一个正整数。你的任务是计算有多少种不同的顺序方法可以用可用的硬币产生一个货币总和x。

例如，如果硬币是{2,3,5}，期望的总和是9，则有3种方法:

2+2+5
3+3+3
2+2+2+3

我试着写这个递归解。
我想出了这个代码。

#include<iostream>
#include<vector>
using namespace std;
#define M 1000000007

vector<int>arr;
vector<vector<int>>dp;
int solve(int i,int target){
if(i>=(int)arr.size()) return 0;
if(target<0) return 0;
if(target==0) return 1;
if(dp[i][target]!=-1) return dp[i][target];
return dp[i][target]=(solve(i,target-arr[i])%M+solve(i+1,target)%M)%M;
}
int main(){
int n,target;
cin>>n>>target;
arr.resize(n);
dp.resize(n+1,vector<int>(target+1,-1));
for(int i=0;i<n;++i){
cin>>arr[i];
}
cout<<solve(0,target);
}

但是这个代码给出了超过时间限制。如何以递归方式编写这些代码以使其被接受?这是一个非递归的方法，但是我想知道如何写一个递归的版本。

Answer 1

一个递归求和的例子，选择结果将是:

void recursive_sum( IN const std::vector<int>& coins, 
IN int result,
OUT std::vector<std::string>& res,
IN std::deque<int> numbers = {},
IN int actual_sum = 0)
{
for(auto& n: coins)
{
int nsum = actual_sum + n; 
if(nsum == result)
insert_result(res, copy_insert(numbers, n));
else if(nsum < result)
recursive_sum(coins, result, res, copy_insert(numbers, n), nsum);
}
}

与此类似的main将完成此工作:

int main()
{
std::vector<std::string> res{};
std::vector<int> coins{};
int sum_result = 0;

input_coins(coins);
input_sum_result(sum_result);
recursive_sum(coins, sum_result, res);
out_result(res);
return 0;
}

如果你想看一下这个例子的完整版本，请点击这里。

输出示例:

"
Insert a number or 'next' to continue
10
Actually coins are: { 10, }
Insert a number or 'next' to continue 
15
Actually coins are: { 10, 15, }
Insert a number or 'next' to continue 
25
Actually coins are: { 10, 15, 25, }
Insert a number or 'next' to continue 
next
Insert the sum result:
100
Possible sums are: 
{10, 10, 10, 10, 10, 10, 10, 10, 10, 10, }
{10, 10, 10, 10, 10, 10, 10, 15, 15, }
{10, 10, 10, 10, 10, 10, 15, 15, 10, }
{10, 10, 10, 10, 10, 10, 15, 25, }
{10, 10, 10, 10, 10, 10, 25, 15, }
{10, 10, 10, 10, 10, 25, 10, 15, }
{10, 10, 10, 10, 10, 25, 25, }
{10, 10, 10, 10, 15, 15, 15, 15, }
{10, 10, 10, 15, 15, 10, 15, 15, }
{10, 10, 10, 15, 15, 15, 25, }
{10, 10, 10, 15, 25, 15, 15, }
{10, 10, 15, 15, 10, 25, 15, }
{10, 10, 15, 15, 15, 10, 10, 15, }
{10, 10, 15, 15, 15, 10, 25, }
{10, 10, 15, 15, 25, 25, }
{10, 15, 15, 15, 15, 15, 15, }
{10, 15, 15, 25, 10, 25, }
{10, 15, 25, 25, 10, 15, }
{10, 15, 25, 25, 25, }
{10, 25, 10, 10, 10, 10, 25, }
{10, 25, 10, 10, 15, 10, 10, 10, }
{15, 15, 15, 15, 15, 25, }
{15, 25, 15, 15, 15, 15, }
{25, 25, 25, 10, 15, }
{25, 25, 25, 15, 10, }
{25, 25, 25, 25, }
"