HDU : Distribute Message


#include <stdio.h>
#include <string.h>

int dp [30 + 5];
int n, m;

int memoization (int curr)
{
    if ( curr == 1 )
        return 1;

    if ( dp [curr] != -1 )
        return dp [curr];

    int ans = 0;
    for ( int i = curr - 1; i >= 1 && i >= curr - m; i-- )
        ans += memoization (i);

    dp [curr] = ans;

    return ans;
}

int main ()
{
    while ( scanf ("%d %d", &n, &m) ) {
        if ( n == 0 && m == 0 )
            break;

        memset (dp, -1, sizeof (dp));

        int z = memoization (n);

        printf ("%d\n", z);
    }

    return 0;
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s