can anyone tell me the solution to this problem i did it in n*a time complexity but for the space n*a it is giving memory exceeded

can anyone tell me how to solve this question in short memory usage

which is less than o(n*a) or o(n*b)

i will be very thankful to you please help me :D

here is my code

#include <stdio.h>

#include <stdlib.h>

int main()

{

int n,o,t;scanf("%d %d %d",&n,&o,&t);

int a[500][300]={0};

int b[500][300]={0};

int i,j,k;

for(i=1;i<=n;i++)

{

for(j=1;j<=i;j++)

{

if(j>o)

break;

if(j==i)

if(j<=o)

a[i][j]=1; ///which shows it is valid

a[i][j]=a[i][j]+b[i-j][0]; ///as the places inc with j we will inc in the table of other above

}

for(k=1;k<=o;k++)

a[i][0]+=a[i][k]; ///total sum of all

for(j=1;j<=i;j++)

{

if(j>t)

break;

if(j==i)

if(j<=t)

b[i][j]=1; ///which shows it is valid

b[i][j]=b[i][j]+a[i-j][0]; ///as the places inc with j we will inc in the table of other above

}

for(k=1;k<=o;k++)

b[i][0]+=b[i][k]; ///total sum of all

}

printf("%d\n",a[n][0]+b[n][0]);

return 0;

}

*Edited by author 13.12.2015 01:13*

Re: can anyone tell me the solution to this problem i did it in n*a time complexity but for the space n*a it is giving memory exceeded

I used idea:

State is - for L songs album there are Sa1, Sa2, ... Saa - counts of albums ends with 1, 2, ... a "My love" songs; Sb1, Sb2, ... Sbb - counts of albums ends with 1, 2, ... b "I miss you" songs.

Total state size is a+b int counters. There is only L state required to calculate (L+1) state.

Re: can anyone tell me the solution to this problem i did it in n*a time complexity but for the space n*a it is giving memory exceeded

Posted by

nadinne 30 Dec 2015 00:55

great idea!