Nson - 1 year ago 65

C++ Question

I am currently trying to make a program which involves ascending sequences. N is for the size of the sequence and K is the maximum number, for example

Input: 2,3

Output: 6 (1,1 - 1,2 - 1,3 - 2,2 - 2,3 - 3,3)

My current code outputs the right answer however it takes way too much time to get to the right answer. What is the fastest solution of this and how do I do the dynamical solution? Here is the code with the slow solution :

`#include<iostream>`

using namespace std;

int n,k,cnt=0,mod=1000000007;

int seq(int n, int k, int first, int depth){

if(depth > n){

cnt = cnt + 1;

return cnt;

}

else {

for(int i=first;i<=k;i++){

seq(n,k,i,depth+1);

}

}

return cnt;

}

int main()

{

cin>>n>>k;

cout<<seq(n,k,1,1)%mod<<"\n";

return 0;

}

Recommended for you: Get network issues from **WhatsUp Gold**. **Not end users.**

Answer Source

I have solved this problem using dynamic programming.

```
#include<bits/stdc++.h>
#define up(j,k,i) for(i=j;i<k;i++)
#define down(j,k,i) for(i=j;i>k;i--)
#define pp(n) printf("%lld\n",n)
#define is(n) scanf("%lld",&n)
#define ips(n) scanf("%lld",n)
#define ss(s) scanf("%s",s)
#define cool 0
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define f(i) cout<<i<<endl;
#define pll pair<lld,lld>
#define pi acos(-1)
#define ds(n,m) scanf("%lld %lld",&n,&m)
#define ts(n,m,k) scanf("%lld %lld %lld",&n,&m,&k)
typedef long double ld;
typedef long long int lld;
using namespace std;
const lld M =1e3+7;
const lld mod=1e9+7;
const lld infi =LLONG_MAX;
lld i,j,ans,k,n,x,y,m,mymax=LLONG_MIN,mymin=LLONG_MAX,b,c,z,sum;
lld dp[M][M],s[M][M];
int main()
{
lld n,k;
ds(n,k);
up(1,k+1,i)
{
s[1][i]=1+s[1][i-1];
}
up(2,n+1,i)
{
up(1,k+1,j)
{
s[i][j]=s[i][j-1]+s[i-1][j];
}
}
pp(s[n][k]);
return 0;
}
```

Recommended from our users: **Dynamic Network Monitoring from WhatsUp Gold from IPSwitch**. ** Free Download**