Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // SOS Dynamic Programming
- // O(n * 2^n)
- //iterative version
- for(int mask = 0; mask < (1<<N); ++mask){
- dp[mask][-1] = A[mask]; //handle base case separately (leaf states)
- for(int i = 0;i < N; ++i){
- if(mask & (1<<i))
- dp[mask][i] = dp[mask][i-1] + dp[mask^(1<<i)][i-1];
- else
- dp[mask][i] = dp[mask][i-1];
- }
- F[mask] = dp[mask][N-1];
- }
- //memory optimized, super easy to code.
- for(int i = 0; i<(1<<N); ++i)
- F[i] = A[i];
- for(int i = 0;i < N; ++i) for(int mask = 0; mask < (1<<N); ++mask){
- if(mask & (1<<i))
- F[mask] += F[mask^(1<<i)];
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement