NEED HELP IN SPACE COMPRESSION IN DP

Revision en1, by javacoder1, 2016-06-03 11:32:46

Hi , was trying to solve the problem

http://mirror.codeforces.com/contest/543/problem/A

using the following algo

for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=b;j++)
            dp[i][j][0]=1;
    }
    for(int k=1;k<=m;k++)
    {
        for(int j=0;j<=b;j++)
        {
            for(int i=1;i<=n;i++)
            {
                dp[i][j][k]=(dp[i-1][j][k]+dp[i][j][k])%mod;
                if(j-arr[i]*1>=0)
                    dp[i][j][k]=(dp[i][j][k]+dp[i][j-arr[i]][(k-1)])%mod;

            }
        }

    }

where dp[i][j][k] means answer for the first i members with maximum error begin j and writing k lines ans is dp[n][b][m] but it's memory is too much.

So i optimised it as

 for(int k=1;k<=m;k++)
    {
        for(int j=0;j<=b;j++)
        {
            for(int i=1;i<=n;i++)
            {
                dp[i][j][k&1]=(dp[i-1][j][k&1]+dp[i][j][k&1])%mod;
                if(j-arr[i]*1>=0)
                    dp[i][j][k&1]=(dp[i][j][k&1]+dp[i][j-arr[i]][(k-1)&1])%mod;

            }
        }
        for(int j=0;j<=b;j++)
        {
            for(int i=1;i<=n;i++)
                dp[i][j][(k-1)&1]=0;
        }
    }

ans is dp[n][b][m&1] but this is getting wrong answer.Someone help.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English javacoder1 2016-06-03 11:32:46 1338 Initial revision (published)