Keeping last n rows of a matrix in C++

Блог пользователя Nidz05

Автор Nidz05, история, 3 года назад, По-английски

Hello, I was wondering if there is a way of keeping last n rows of a matrix efficiently in C++, for example for DP?

dynamic programming, matrix, memory optimization

-4

Nidz05
3 года назад
4

Комментарии (4)

Написать комментарий?

Gassa

3 года назад, скрыть # |

In any language, the simplest approach is to just keep the array as [n][width] instead of [height][width], and access elements as [row % n][col] instead of [row][col].

→ Ответить

Nidz05

3 года назад, скрыть # ^ |

vector<vector<ll>> dp;

int main()
{
    SPED;
    ll n,k,t;
    cin >> n >> k >> t;
    vector<int> a(n+1);
    fff(i,1,n)
    cin >> a[i];
    ll raz = n-k*t;
    if(raz<k)
    {
        dp = vector<vector<ll>>(n+1,vector<ll>(raz+1,-INF));
        dp[0][0]=0;
        fff(i,1,n)
        {
            fff(j,0,raz)
            {
                if(j-1>=0)
                    dp[i][j]=max(dp[i][j],dp[i-1][j-1]);
                if(i-t>=0)
                    dp[i][j]=max(dp[i][j],dp[i-t][j]+a[i-t+1]);
            }
        }
        cout << dp[n][raz] << "\n";
    }
    else
    {
        dp = vector<vector<ll>>(n+1,vector<ll>(k+1,-INF));
        dp[0][0]=0;
        fff(i,1,n)
        {
            fff(j,0,k)
            {
                dp[i][j]=dp[i-1][j];
                if(j-1>=0 && i-t>=0)
                    dp[i][j]=max(dp[i][j],dp[i-t][j-1]+a[i-t+1]);
            }
        }
        cout << dp[n][k] << "\n";
    }
    return 0;
}

What if i have something like this and i want to keep last t rows of dp but i am also updating the dp like so?

→ Ответить

Gassa

3 года назад, скрыть # ^ |

+11

You have, for example (less lines to keep my comment short):

fff(i,1,n)
    fff(j,0,raz) {
        if(j-1>=0) dp[i][j]=max(dp[i][j],dp[i-1][j-1]);
        if(i-t>=0) dp[i][j]=max(dp[i][j],dp[i-t][j]+a[i-t+1]);
    }
cout << dp[n][raz] << "\n";

Transform it to:

fff(i,1,n)
    fff(j,0,raz) {
        if(j-1>=0) dp[i%(t+1)][j]=max(dp[i%(t+1)][j],dp[(i-1)%(t+1)][j-1]);
        if(i-t>=0) dp[i%(t+1)][j]=max(dp[i%(t+1)][j],dp[(i-t)%(t+1)][j]+a[i-t+1]);
    }
cout << dp[n%(t+1)][raz] << "\n";

Is it any different from what you initially asked?

→ Ответить