Return to Question

Question Link

Consider a money system consisting of n coins. Each coin has a positive integer value. Your task is to calculate the number of distinct ordered ways you can produce a money sum x using the available coins.

For example, if the coins are {2,3,5} and the desired sum is 9, there are 3 ways:

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

I am trying to write recursive solution for this.
I came up with this code.

#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);
}

but this code is giving time-limit-exceeded. What can I do to improve the performance so that it gets accepted?

Here is an iterative version but I'd like to keep the recursive approach if I can.

Question Link

Consider a money system consisting of n coins. Each coin has a positive integer value. Your task is to calculate the number of distinct ordered ways you can produce a money sum x using the available coins.

For example, if the coins are {2,3,5} and the desired sum is 9, there are 3 ways:

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

The return value is to be printed modulo 10⁹+7.

I am trying to write recursive solution for this.
I came up with this code.

#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);
}

but this code is giving time-limit-exceeded. What can I do to improve the performance so that it gets accepted?

Here is an iterative version but I'd like to keep the recursive approach if I can.

Question Link

Consider a money system consisting of n coins. Each coin has a positive integer value. Your task is to calculate the number of distinct ordered ways you can produce a money sum x using the available coins.

For example, if the coins are {2,3,5} and the desired sum is 9, there are 3 ways:

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

I am trying to write recursive solution for this.
I came up with this code.

#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);
}

but this code is giving time-limit-exceeded. How can this code be written in a recursive manner so that it gets accepted? Here is non-recursive approach but I want to know how to write a recursive version of this.

Question Link

Consider a money system consisting of n coins. Each coin has a positive integer value. Your task is to calculate the number of distinct ordered ways you can produce a money sum x using the available coins.

For example, if the coins are {2,3,5} and the desired sum is 9, there are 3 ways:

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

I am trying to write recursive solution for this.
I came up with this code.

#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);
}

but this code is giving time-limit-exceeded. What can I do to improve the performance so that it gets accepted? 

Here is an iterative version but I'd like to keep the recursive approach if I can.

Question Link

Consider a money system consisting of n coins. Each coin has a positive integer value. Your task is to calculate the number of distinct ordered ways you can produce a money sum x using the available coins.

For example, if the coins are {2,3,5} and the desired sum is 9, there are 3 ways:

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

I am trying to write recursive solution for this.
I came up with this code.

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;
}

but this code is giving time-limit-exceeded. How can this code be written in a recursive manner so that it gets accepted? Here is non-recursive approach but I want to know how to write a recursive version of this.

Question Link

Consider a money system consisting of n coins. Each coin has a positive integer value. Your task is to calculate the number of distinct ordered ways you can produce a money sum x using the available coins.

For example, if the coins are {2,3,5} and the desired sum is 9, there are 3 ways:

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

I am trying to write recursive solution for this.
I came up with this code.

#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);
}

but this code is giving time-limit-exceeded. How can this code be written in a recursive manner so that it gets accepted? Here is non-recursive approach but I want to know how to write a recursive version of this.