|
|
back to boardcan 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! |
|
|