c++ - How do i reduce my DP(Dynamic Programming) state? -


i trying problem: http://www.spoj.com/problems/bud13tlf/

the problem dp state: have recursion as: let k=space left,visited[ ] array keep track of visited elements , array a[ ] represent w1,w2,..wn. , function int solve (k , visited[ ]) function returns ans function:

int solve(int k,vector<bool> vis){      if(k<0)return 0;     if(k==0)return 1;     int ans=1;     loop(i,n){         if(!vis[i]){             vis[i]=1;             ans+=solve(k-a[i],vis)%mod;             vis[i]=0;int j;             for(j=i+1;a[j]==a[i];j++);             j--;             i=j;         }     }     if(ans!=1) ans--;     return ans; } 

the problem how define dp state because visited(vector/array) can huge (max 2^100 possibilities if choose bitmasks or bitsets)? please comment on how can represent dp state if dp state depends on whole array ?


Comments

Popular posts from this blog

android - InAppBilling registering BroadcastReceiver in AndroidManifest -

python Tkinter Capturing keyboard events save as one single string -

sql server - Why does Linq-to-SQL add unnecessary COUNT()? -